1994 AIME Problems/Problem 11
Problem
Ninety-four bricks, each measuring are to be stacked one on top of another to form a tower 94 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 ninety-four of the bricks?
Solutions
Solution 1
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
inches,
inches, or
inches to the height. Now all we need to do is to find the different change values we can get from
's,
's, and
's. Because
,
, and
are all multiples of
, the change will always be a multiple of
, so we just need to find the number of changes we can get from
's,
's, and
's.
From here, we count what we can get:
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 for
being positive integers is
.
But we also have a maximum change (), 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
's,
's, or
's. The maximum we can't get is
, so the numbers
and below, except
and
, 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
(and
),
doesn't since
is not divisible by
or
,
does since
, and
and
don't, and
does.
Thus the numbers ,
,
all the way to
,
,
,
, and
work. That's
numbers. That's the number of changes you can make to a stack of bricks with dimensions
, including not changing it at all.
Solution 2
Using bricks of dimensions is comparable to using bricks of dimensions
which is comparable to using bricks of dimensions
. Using 5 bricks of height
can be replaced by using 2 bricks of height
and 3 bricks of height
.
It follows that all tower heights can be made by using 4 or fewer bricks of height . There are
ways to build a tower using 4 or fewer bricks of height
. Taking the heights
, we see that towers using a different number of bricks of height
have unequal heights. Thus, all of the
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.