Question: Hi,
My daughter asked me for help with a question she was given by her math teacher for extra study. I find myself stumped. Can you help? The question is as follows...

You have 4 bricks each with dimensions of 4" X 5" X 9". If you pile the 4 bricks on top of each other to form a tower how many different tower heights can be achieved? All four bricks must be used in each tower.

Thanks,
Mike

Mike,

Actually the answer is one: once I pile up the bricks, say using 4" as the height on the bottom brick, then again 4", then 9" and 5", I have a tower of height 22", but all my bricks are used, so I cannot build a second tower, say using the numbers 9, 9, 5, 5. They probably mean "How many different tower heights COULD be achieved by piling up four bricks of dimensions 4" X 5" X 9" atop each other". Combinatorics is about counting possibilities rather than realizations, and this is more abstract. I think that the questions should be worded carefully, to reflect this fact.

Now, how many possibilities are there exactly? For each brick I can use any of the three different dimensions as the height. So there are 3 possible heights for the bottom brick, 3 also for the second brick, 3 for the third and 3 for the top brick, giving 3*3*3*3 = 81 possible tower models. However, different tower models can have the same height: If I were to use 4" height on the top and bottom bricks and 9" height on the two middle bricks, the tower would be different in shape than if I would use 9" height on the top and bottom bricks and 4" height on the two middle bricks, though the two models have the same height. It turns out that the height of the tower only depends on the number of times each dimension was used for the height. Let A, B, C respectively denote the number of times 4", 5" and 9" is used as the height of a brick. The number of possible tower heights turns out to be the number of integer solutions to A + B + C = 4.

There are two things to say about this:

1. It is not that hard to list all the possible solutions : (4,0,0), (3,1,0), (3,0,1), (2,2,0), ..., (0,0,4) and count them to realize that there are 15 of them. Another way to go is to use the formula if you know it: The number of integer solutions to x₁ + x₂ + ... + x_k = n is {(n + k - 1) choose n}.
   
   
2. If the bricks were 1" by 2" by 4", I could achieve a height of 10" with brick heights of 1", 1", 4", 4", but also with 2", 2", 2", 4". Therefore there would be less than 15 possible tower heights. This does not happen with the dimensions 4", 5" and 9", but it is not completely obvious and you need to explain why.