Counting Patterns in Stacking BricksDate: 01/04/2009 at 00:44:50 From: Matth Subject: arranging bricks I have a number of bricks which are each 3 units long, 1 unit deep and 1 unit wide. I want to stack them in a tower 3 units wide, 1 unit deep and 10 units high. How many ways can that be done? I have got 19 as my answer and 28 is the correct answer. I don't know how? First I got 6 combinations with arranging the bricks in 2 groups of 3 vertically and 2 groups of 2 horizontally. Next I got 4 combinations with arranging the bricks in 3 groups of 3 vertically and 1 horizontally. Then I got 8 with using 3 vertically and 7 horizontally. I also got 1 with using 10 horizontally. So 6 + 4 + 8 + 1 = 19. I cannot get the remaining 9 combinations. Date: 01/04/2009 at 03:58:02 From: Doctor Greenie Subject: Re: arranging bricks Hi, Matth -- You found the combinations using 2 groups of 3 vertically if the remaining 4 bricks are in 2 groups of 2, but you overlooked two other possibilities with 2 groups of 3 vertically--the remaining 4 bricks can be in a group of 3 and a single, or in a group of 2 and 2 singles. You can get the final answer of 28 if you find the correct numbers of ways to get combinations of those types. However, you will find it quite a bit more difficult to count the numbers of these combinations. While your approach to the problem using the different possible combinations of vertical and horizontal groups is good, there is another approach to problems of this type which makes it easier to find the answer--especially if, in an example like yours, we want to find the number of ways if the tower is to be 20 or 100 bricks high instead of 10. We can solve problems like this using recursive formulas. That is, we can find a pattern for the number of ways to build a tower "k" bricks high in terms of the numbers of ways to build shorter towers. Here is how the analysis might go for your particular problem. (1) If the tower is only 1 brick high, then there is clearly only 1 way to build it--1 horizontal brick. N(1) = 1 (2) If the tower is 2 bricks high, there is still only 1 way to build it--2 horizontal bricks. N(2) = 1 (3) If the tower is 3 bricks high, then there are 2 ways to build it--3 horizontal bricks, or 3 vertical bricks. N(3) = 2 Now, for a tower 4 bricks high, let's think about the ways we can "finish" building the tower. We can either have a tower 3 bricks high and finish with a horizontal brick; or we can have a tower 1 brick high and finish with 3 vertical bricks. The number of ways we can have a tower 3 bricks high and finish with a horizontal brick is the number of ways to build a tower 3 bricks high: N(3) = 2 And the number of ways we can have a tower 1 brick high and finish with 3 vertical bricks is the number of ways to build a tower 1 brick high: N(1) = 1 And so the total number of ways to build a tower 4 bricks high is N(4) = N(3) + N(1) = 2+1 = 3 And next, for finishing a tower 5 bricks high, we can either have a tower 4 bricks high and finish with a horizontal brick; or we can have a tower 2 bricks high and finish with 3 vertical bricks. The number of ways we can have a tower 4 bricks high and finish with a horizontal brick is the number of ways to build a tower 4 bricks high: N(4) = 3 And the number of ways we can have a tower 2 bricks high and finish with 3 vertical bricks is the number of ways to build a tower 2 bricks high: N(2) = 1 And so the total number of ways to build a tower 5 bricks high is N(5) = N(4) + N(2) = 3+1 = 4 The analysis will be the same for higher towers. We can see that, for a tower "k" bricks high, the number of ways to build it is N(k) = N(k-1) + N(k-3) And so we can form a "recursive" formula for finding the number of ways to build a tower k bricks high: N(1) = 1 N(2) = 1 N(3) = 2 for k > 3, N(k) = N(k-1) + N(k-3) We can use this recursive formula to find the number of ways to build the tower 10 bricks high: N(1) = 1 N(2) = 1 N(3) = 2 N(4) = N(3)+N(1) = 2+1 = 3 N(5) = N(4)+N(2) = 3+1 = 4 N(6) = N(5)+N(3) = 4+2 = 6 N(7) = N(6)+N(4) = 6+3 = 9 N(8) = N(7)+N(5) = 9+4 = 13 N(9) = N(8)+N(6) = 13+6 = 19 N(10) = N(9)+N(7) = 19+9 = 28 I hope this helps; and I hope you find it as fascinating as I did when I first saw it at about your age.... - Doctor Greenie, The Math Forum http://mathforum.org/dr.math/ Date: 01/04/2009 at 08:14:25 From: Matth Subject: Thank you (arranging bricks) Thanks very much for that help. I was struggling with it for a long time. Thanks again. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/