Paving Paths
How many different ways can I lay 10 paving slabs, each 2 foot by 1 foot, to make a path 2 foot wide and 10 foot long from my back door into my garden, without cutting any of the paving slabs?
Well done Michael Brooker, age 9, home educated and Chris Waterhouse, Hethersett High School, Norfolk, for spotting the Fibonacci sequence here and finding that there are 89 different ways to lay the 10 paving slabs. Each slab is 2 foot by 1 foot and a path has to be made 2 foot wide and 10 foot long from my back door into my garden, without cutting any of the paving slabs. Chris drew all the different patterns for 1,2,3,4 and 5 slabs and you can try this for yourself. Here is Michael's solution:
I make the answer 89.
- I first decided that it had something to do with sequences.
- Then I drew a few and wrote them as numbers, with 0 standing for a vertical brick and 1 standing for two horizontal bricks.
- But there was no pattern I could see!
- So I did it in a different way. I worked out the number of ways of arranging single and double bricks on areas the size of 1, 2, 3, 4, 5, and 6 single bricks. They formed the start of the so-called Fibonacci series. Therefore I worked out the 7th, 8th, 9th, and 10th numbers in the series.
- Obviously the tenth number, which equals 89, is the answer to the whole problem.
Having spotted the Fibonacci sequence it is necessary to PROVE that it works to give the right answer for 10 slabs, or better still that it woks for any number of slabs.
Supposing you have to lay n slabs. When you have laid (n - 2) slabs, in any one of the many possible ways, you can lay 2 more, making n altogether, laying them 'lengthwise' along the path (like slabs 2 and 3 in the diagram). All these arrangements will give you different patterns from the ones you get by laying (n - 1) slabs, then laying just one more across the path (like slab 4 in the diagram). This proves that the number of patterns for n slabs is the sum of the number of patterns for (n - 2) and for (n -1) which is the rule for generating the Fibonacci sequence.
Another way to do this problem is to work out the number of arrangements with 5 pairs lengthwise and no slabs across the path (just 1); the number with 4 pairs lengthwise and 2 across (15 ways); the number with 3 pairs lengthwise and 4 across (35 ways); the number with 2 pairs lengthwise and 6 across (28 ways); the number with one pair lengthwise and 8 across (9 ways); and the number with no pairs lengthwise and all 10 across (1 way). Although this is not so efficient as using the Fibonacci sequence it does provide a challenge in itself and, for those who like to do it, we have given the answers here so they can check their work.