Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1994 AIME Problems/Problem 11

Revision as of 12:06, 21 July 2012 by Fro116 (talk | contribs) (→‎Solution)

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

Solution 1

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. Because $0$, $6$, and $15$ are all multiples of $3$, 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.

Solution 2

Using bricks of dimensions $4''\times10''\times19''$ is comparable to using bricks of dimensions $0''\times6''\times15''$ which is comparable to using bricks of dimensions $0''\times2''\times5''$. Using 5 bricks of height $2''$ can be replaced by using 2 bricks of height $5''$ and 3 bricks of height $0''$.

It follows that all tower heights can be made by using 4 or fewer bricks of height $2''$. There are $95+94+93+92+91=465$ ways to build a tower using 4 or fewer bricks of height $2''$. Taking the heights $\mod 5$, we see that towers using a different number of bricks of height $2''$ have unequal heights. Thus, all of the $\boxed{465}$ tower heights are different.

See also

1994 AIME (Problems • Answer Key • Resources)
Preceded by
Problem 10 		Followed by
Problem 12
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1994_AIME_Problems/Problem_11&oldid=47681"