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"

m
m (→‎Solution 1)
(10 intermediate revisions by 10 users not shown)
Line 1: Line 1:
−
{{empty}}
 
 
== Problem ==
 
== Problem ==
 +
Ninety-four bricks, each measuring <math>4''\times10''\times19'',</math> are to be stacked one on top of another to form a tower 94 bricks tall.  Each brick can be oriented so it contributes <math>4''\,</math> or <math>10''\,</math> or <math>19''\,</math> to the total height of the tower.  How many different tower heights can be achieved using all ninety-four of the bricks?
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
=== Solution 1 ===
 +
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:
 +
 
 +
<cmath>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</cmath>
 +
 
 +
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 <math>2m + 5n</math> for <math>m,n</math> being [[positive integer]]s is <math>5 \times 2 - 5 - 2=3</math>.
 +
 
 +
But we also have a maximum change (<math>94 \times 5</math>), 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 <math>0</math>'s, <math>3</math>'s, or <math>5</math>'s. The maximum we can't get is <math>5 \times 3-5-3=7</math>, so the numbers <math>94 \times 5-8</math> and below, except <math>3</math> and <math>1</math>, work. Now there might be ones that we haven't counted yet, so we check all numbers between <math>94 \times 5-8</math> and <math>94 \times 5</math>. <math>94 \times 5-7</math> obviously doesn't work, <math>94 \times 5-6</math> does since 6 is a multiple of 3, <math>94 \times 5-5</math> does because it is a multiple of <math>5</math> (and <math>3</math>), <math>94 \times 5-4</math> doesn't since <math>4</math> is not divisible by <math>5</math> or <math>3</math>, <math>94 \times 5-3</math> does since <math>3=3</math>, and <math>94 \times 5-2</math> and <math>94 \times 5-1</math> don't, and <math>94 \times 5</math> does.
 +
 
 +
Thus the numbers <math>0</math>, <math>2</math>, <math>4</math> all the way to <math>94 \times 5-8</math>, <math>94 \times 5-6</math>, <math>94 \times 5-5</math>, <math>94 \times 5-3</math>, and <math>94\times 5</math> work. That's <math>2+(94 \times 5 - 8 - 4 +1)+4=\boxed{465}</math> numbers. That's the number of changes you can make to a stack of bricks with dimensions <math>4 \times 10 \times 19</math>, including not changing it at all.
 +
 
 +
=== Solution 2 ===
 +
Using bricks of dimensions <math> 4''\times10''\times19'' </math> is comparable to using bricks of dimensions <math> 0''\times6''\times15'' </math> which is comparable to using  bricks of dimensions <math> 0''\times2''\times5''</math>. Using 5 bricks of height <math>2''</math> can be replaced by using 2 bricks of height <math>5''</math> and 3 bricks of height <math>0''</math>.
 +
 
 +
It follows that all tower heights can be made by using 4 or fewer bricks of height <math>2''</math>. There are <math>95+94+93+92+91=465</math> ways to build a tower using 4 or fewer bricks of height <math>2''</math>. Taking the heights <math>\mod 5</math>, we see that towers using a different number of bricks of height <math>2''</math> have unequal heights. Thus, all of the <math>\boxed{465}</math> tower heights are different.
 +
 
 
== See also ==
 
== See also ==
−
* [[1994 AIME Problems/Problem 10 | Previous problem]]
+
{{AIME box|year=1994|num-b=10|num-a=12}}
−
* [[1994 AIME Problems/Problem 12 | Next problem]]
+
 
−
* [[1994 AIME Problems]]
+
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Revision as of 14:12, 15 July 2019

Problem

Ninety-four bricks, each measuring $4''\times10''\times19'',$ are to be stacked one on top of another to form a tower 94 bricks tall. Each brick can be oriented so it contributes $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 19$, 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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1994_AIME_Problems/Problem_11&oldid=107653"