Laying Paving Stones
Date: 11/28/2001 at 09:04:25 From: Brian Subject: Sequences - problem My son is stuck on his course work. Can you help with finding the relation for the following sequence that relates to the number of ways that paving stones can be laid to make a 3-foot-wide path using 3-foot by 1-foot stones? Length of path 5 6 7 8 9 Number of ways 4 6 9 13 19 We are unable to find the relation and hence can not move on generalising the relation for the nth term. Have we got the number of ways right? Any ideas on how to proceed?
Date: 11/28/2001 at 13:09:12 From: Doctor Peterson Subject: Re: Sequences - problem Hi, Brian. I always prefer to look not just at the numbers you get, but at HOW you got the numbers. A good way of counting often contains within itself a rule that can be used to describe the relation. If you just tried randomly to find all the ways you could make a path, then you can't be sure of your numbers, and have not learned much about where they come from. But if you looked for an orderly method, then you are close to a solution. We might do better starting with a one-foot path, because the rule often shows up best with the simplest numbers (though it might get a little more complicated for larger numbers): Length: 1 2 3 4 Ways: 1 1 2 I haven't worked out the number for a 4-foot path yet. How can I make this counting easy? I would take it one stone at a time: once I've placed the first stone, how many ways are there to place the rest? The first stone can be either lengthwise or crosswise: +-+-+-+-+ +-+-+-+-+ |===== | || | |===== | or || | |===== | || | +-+-+-+-+ +-+-+-+-+ If it is lengthwise, the space next to it can only be filled with two more lengthwise stones, as shown. In either case, you now have a smaller path left to fill in, either 1 foot or 3 feet long. But we already know how many ways there are to do that! So the number of ways to make a 4-foot path is the sum of the ways to make a 1-foot and a 3-foot path. I can fill in the missing space with "3": +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ |===== || || =====| || | | || |===== || or || =====| or || | | || |===== || || =====| || | | || +-+-+-+-+ +-+-+-+-+ +-+-+-+-+ \_______/ \______________________/ 1 2 Now, can you see a way to use this method, first to check the numbers you have, and then to find a recursive formula for the sequence? Work this out, and then look at this answer to a similar problem: Brick Patterns http://mathforum.org/dr.math/problems/jessi9.17.97.html - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum