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"

(I don't want to be the only guy trying to solve hard problems here...)
(→‎Problem)
 
(10 intermediate revisions by 10 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
Ninety-four bricks, each measuring <math>4''\times10''\times19'',</math> are to stacked one on top of another to form a tower 94 bricks tall.  Each brick can be oriented so it contribues <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?
+
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 of the ninety-four bricks?
  
−
== Solution ==
+
== Solutions ==
−
We have the smallest stack, which has a height of <math>94*4</math> 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. From there, 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.
+
=== 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:
 
From here, we count what we can get:
  
−
0, 2, 4, 5, 6, 7, 8, 9, 10, ......
+
<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>
  
−
So it seems we can get every integer greater or equal to four. The [[Chicken McNugget Theorem]] says that the greatest we can't get is <math>5*2-5-2=3</math>, so that verifies it. But we have a maximum change(94*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 <math>5*3-5-3=7</math>, so the numbers <math>94*5-8</math> and below, except 3 and 1, work. Now there might be ones that we haven't counted yet, so we check all numbers between <math>94*5-8</math> and <math>94*5</math>. <math>94*5-7</math> obviously doesn't work, <math>94*5-6</math> does since 6 is a multiple of 3, <math>94*5-5</math> does because it is a multiple of 5(and 3), <math>94*5-4</math> doesn't since 4 is not divisible by 5 or 3, <math>94*5-3</math> does since 3=3, and <math>94*5-2</math> and <math>94*5-1</math> don't, and <math>94*5</math> does.
+
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>.  
  
−
Thus the numbers 0, 2, 4 to 94*5-8, 94*5-6, 94*5-5, 94*5-3, and 94*5 work. That's <math>2+(94*5-8-4+1)+4=\boxed{485}</math> numbers. That's the number of changes you can make to a stack of bricks with dimensions 4*10*14, including not changing it at all.
+
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 ==
Line 17: Line 25:
  
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 23:45, 15 November 2024

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 of the ninety-four bricks?

Solutions

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