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

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

(tex)
(→‎Solution)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
−
We have the smallest stack, which has a height of <math>94 \times 4</math> inches. Now when we change the height of one of the bricks, we either add <math>0</math> inches, <math>6</math> inches, or <math>15</math> inches to the height. Now all we need to do is to find the different change values we can get from <math>94</math> <math>0</math>'s, <math>6</math>'s, and <math>15</math>'s. From there, the change will always be a multiple of <math>3</math>, so we just need to find the number of changes we can get from <math>0</math>'s, <math>2</math>'s, and <math>5</math>'s.
+
We have the smallest stack, which has a height of <math>94 \times 4</math> inches. Now when we change the height of one of the bricks, we either add <math>0</math> inches, <math>6</math> inches, or <math>15</math> inches to the height. Now all we need to do is to find the different change values we can get from <math>94</math> <math>0</math>'s, <math>6</math>'s, and <math>15</math>'s. Because <math>0</math>, <math>6</math>, and <math>15</math> are all multiples of <math>3</math>, the change will always be a multiple of <math>3</math>, so we just need to find the number of changes we can get from <math>0</math>'s, <math>2</math>'s, and <math>5</math>'s.
  
 
From here, we count what we can get:
 
From here, we count what we can get:

Revision as of 19:17, 12 March 2012

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. 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.

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=45424"