# 1994 AIME Problems/Problem 11

## Problem

Ninety-four bricks, each measuring $4''\times10''\times19'',$ are to stacked one on top of another to form a tower 94 bricks tall. Each brick can be oriented so it contribues $4''\,$ or $10''\,$ or $19''\,$ 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 $94 \times 4$ 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 = 2, 4 = 2+2, 5 = 5, 6 = 2+2+2, 7 = 5+2, 8 = 2+2+2+2, 9 = 5+2+2, \ldots$$

It seems we can get every integer greater or equal to four; we can easily deduce this by considering parity or using the Chicken McNugget Theorem, which says that the greatest number that cannot be expressed in the form of $2m + 5n$ for $m,n$ being positive integers is $5 \times 2 - 5 - 2=3$.

But we also have a maximum change ($94 \times 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 $5 \times 3-5-3=7$, so the numbers $94 \times 5-8$ and below, except $3$ and $1$, work. Now there might be ones that we haven't counted yet, so we check all numbers between $94 \times 5-8$ and $94 \times 5$. $94 \times 5-7$ obviously doesn't work, $94 \times 5-6$ does since 6 is a multiple of 3, $94 \times 5-5$ does because it is a multiple of $5$ (and $3$), $94 \times 5-4$ doesn't since $4$ is not divisible by $5$ or $3$, $94 \times 5-3$ does since $3=3$, and $94 \times 5-2$ and $94 \times 5-1$ don't, and $94 \times 5$ does.

Thus the numbers $0$, $2$, $4$ all the way to $94 \times 5-8$, $94 \times 5-6$, $94 \times 5-5$, $94 \times 5-3$, and $94\times 5$ work. That's $2+(94 \times 5 - 8 - 4 +1)+4=\boxed{465}$ numbers. That's the number of changes you can make to a stack of bricks with dimensions $4 \times 10 \times 14$, including not changing it at all.