1994 AIME Problems/Problem 11

Problem

Ninety-four bricks, each measuring are to stacked one on top of another to form a tower 94 bricks tall. Each brick can be oriented so it contribues or or to the total height of the tower. How many different tower heights can be achieved using all ninety-four of the bricks?

Solution

We have the smallest stack, which has a height of inches. Now when we change the height of one of the bricks, we either add 0 inches, 6 inches, or 15 inches to the height. Now all we need to do is to find the different change values we can get from 94 0's, 6's, and 15's. From there, the change will always be a multiple of 3, so we just need to find the number of changes we can get from 0's, 2's, and 5's.

From here, we count what we can get:

0, 2, 4, 5, 6, 7, 8, 9, 10, ......

So it seems we can get every integer greater or equal to four. The Chicken McNugget Theorem says that the greatest we can't get is , so that verifies it. But we have a maximum change(94*5), so that will have to stop somewhere. To find the gaps, we can work backwards as well. From the maximum change, we can subtract either 0's, 3's, or 5's. The maximum we can't get is , so the numbers and below, except 3 and 1, work. Now there might be ones that we haven't counted yet, so we check all numbers between and . obviously doesn't work, does since 6 is a multiple of 3, does because it is a multiple of 5(and 3), doesn't since 4 is not divisible by 5 or 3, does since 3=3, and and don't, and does.

Thus the numbers 0, 2, 4 to 94*5-8, 94*5-6, 94*5-5, 94*5-3, and 94*5 work. That's numbers. That's the number of changes you can make to a stack of bricks with dimensions 4*10*14, including not changing it at all.