Difference between revisions of "1994 AIME Problems/Problem 11"

Revision as of 18:28, 4 July 2013

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.

Revision as of 12:06, 21 July 2012 (view source) Fro116 (talk \| contribs) (→‎Solution) ← Older edit		Revision as of 18:28, 4 July 2013 (view source) Nathan wailes (talk \| contribs) Newer edit →
Line 25:		Line 25:

	[[Category:Intermediate Combinatorics Problems]]		[[Category:Intermediate Combinatorics Problems]]
		+	{{MAA Notice}}

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

Page

Toolbox

Search