Problem:
Ninety-four bricks, each measuring , are to be stacked one on top of another to form a tower bricks tall. Each brick can be oriented so it contributes or or to the total height of the tower. How many different tower heights can be achieved using all of the bricks?
Solution:
If five bricks in a tower are oriented so that each contributes to the height of the tower, then these five bricks contribute to the height of the tower. These five bricks can be reoriented so that three contribute each and two contribute to the height of the tower. Note that with this reorientation, the total height of the tower is unchanged. Thus we may assume that in a tower of bricks there are , or bricks oriented so that they each contribute to the total height. All other bricks in the tower are oriented to contribute or to the height.
Suppose that there are blocks that contribute and blocks that contribute to the height of the tower. Then there are bricks that contribute , and the height of the tower is
inches. As noted above, we may assume that . Because we must have , so there are possible values for . In all there are such pairs , and hence at most different possible tower heights.
We now show that any two of these ordered pairs give different tower heights. Suppose that ordered pairs and lead to towers of the same height. Then
It follows that , which implies that is divisible by . Because we conclude that and then that . Thus the ordered pairs correspond to different tower heights.
If we have bricks, bricks and bricks in our tower, then and the height of the tower is
There will be a height corresponding to each possible value of where and are non-negative integers with . With these restrictions, we have
To count the number of possible values of we apply the following theorem:
If , then every integer greater than or equal to can be written as where and are nonnegative integers, and the number of nonnegative integers that cannot be written in this way is .
Define an integer between and to be "good" if can be written as where and , and "bad" otherwise. By the theorem quoted, there are bad integers between and (namely and ). Substituting , we see that an integer between and is good if and only if
for some nonnegative integers and . Thus by the theorem stated above there are bad integers between and (namely , , , and ). Hence the number of good integers and the desired number of tower heights is .
The problems on this page are the property of the MAA's American Mathematics Competitions