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 "2006 AIME I Problems/Problem 11"

m
(→‎Solution)
 
(11 intermediate revisions by 8 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
A collection of 8 cubes consists of one cube with edge-length <math> k </math> for each integer <math> k, 1 \le k \le 8. </math> A tower is to be built using all 8 cubes according to the rules:  
+
A collection of 8 [[cube (geometry) | cube]]s consists of one cube with [[edge]]-[[length]] <math> k </math> for each [[integer]] <math> k, 1 \le k \le 8. </math> A tower is to be built using all 8 cubes according to the rules:  
  
 
* Any cube may be the bottom cube in the tower.
 
* Any cube may be the bottom cube in the tower.
 
* The cube immediately on top of a cube with edge-length <math> k </math> must have edge-length at most <math> k+2. </math>  
 
* The cube immediately on top of a cube with edge-length <math> k </math> must have edge-length at most <math> k+2. </math>  
  
−
Let <math> T </math> be the number of different towers than can be constructed. What is the remainder when <math> T </math> is divided by 1000?
+
Let <math> T </math> be the number of different towers than can be constructed. What is the [[remainder]] when <math> T </math> is divided by 1000?
−
 
 
−
 
 
−
 
 
−
 
 
  
 
== Solution ==
 
== Solution ==
 +
We proceed [[recursion | recursively]].  Suppose we can build <math>T_m</math> towers using blocks of size <math>1, 2, \ldots, m</math>.  How many towers can we build using blocks of size <math>1, 2, \ldots, m, m + 1</math>?  If we remove the block of size <math>m + 1</math> from such a tower (keeping all other blocks in order), we get a valid tower using blocks <math>1, 2, \ldots, m</math>.  Given a tower using blocks <math>1, 2, \ldots, m</math> (with <math>m \geq 2</math>), we can insert the block of size <math>m + 1</math> in exactly 3 places: at the beginning, immediately following the block of size <math>m - 1</math> or immediately following the block of size <math>m</math>.  Thus, there are 3 times as many towers using blocks of size <math>1, 2, \ldots, m, m + 1</math> as there are towers using only <math>1, 2, \ldots, m</math>.  There are 2 towers which use blocks <math>1, 2</math>, so there are <math>2\cdot 3^6 = 1458</math> towers using blocks <math>1, 2, \ldots, 8</math>, so the answer is <math>\boxed{458}</math>.
  
 +
(Note that we cannot say, "there is one tower using the block <math>1</math>, so there are <math>3^7</math> towers using the blocks <math>1, 2, \ldots, 8</math>."  The reason this fails is that our recursion only worked when <math>m \geq 2</math>: when <math>m = 1</math>, there are only 2 places to insert a block of size <math>m + 1 = 2</math>, at the beginning or at the end, rather than the 3 places we have at later stages.  Also, note that this method generalizes directly to seeking the number of towers where we change the second rule to read, "The cube immediately on top of a cube with edge-length <math>k</math> must have edge-length at most <math>k + n</math>," where <math>n</math> can be any fixed integer.)
  
 +
== Video Solution by OmegaLearn ==
 +
https://youtu.be/WpSpnx8PPnc?t=732
  
 +
~ pi_is_3.14
  
 
== See also ==
 
== See also ==
−
* [[2006 AIME I Problems]]
+
* [https://www.artofproblemsolving.com/wiki/index.php?title=2015_AIME_II_Problems/Problem_10 2015 AIME II Problem 10]
 +
{{AIME box|year=2006|n=I|num-b=10|num-a=12}}
 +
 
 +
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 04:40, 4 November 2022

Problem

A collection of 8 cubes consists of one cube with edge-length $k$ for each integer $k, 1 \le k \le 8.$ A tower is to be built using all 8 cubes according to the rules:

  • Any cube may be the bottom cube in the tower.
  • The cube immediately on top of a cube with edge-length $k$ must have edge-length at most $k+2.$

Let $T$ be the number of different towers than can be constructed. What is the remainder when $T$ is divided by 1000?

Solution

We proceed recursively. Suppose we can build $T_m$ towers using blocks of size $1, 2, \ldots, m$. How many towers can we build using blocks of size $1, 2, \ldots, m, m + 1$? If we remove the block of size $m + 1$ from such a tower (keeping all other blocks in order), we get a valid tower using blocks $1, 2, \ldots, m$. Given a tower using blocks $1, 2, \ldots, m$ (with $m \geq 2$), we can insert the block of size $m + 1$ in exactly 3 places: at the beginning, immediately following the block of size $m - 1$ or immediately following the block of size $m$. Thus, there are 3 times as many towers using blocks of size $1, 2, \ldots, m, m + 1$ as there are towers using only $1, 2, \ldots, m$. There are 2 towers which use blocks $1, 2$, so there are $2\cdot 3^6 = 1458$ towers using blocks $1, 2, \ldots, 8$, so the answer is $\boxed{458}$.

(Note that we cannot say, "there is one tower using the block $1$, so there are $3^7$ towers using the blocks $1, 2, \ldots, 8$." The reason this fails is that our recursion only worked when $m \geq 2$: when $m = 1$, there are only 2 places to insert a block of size $m + 1 = 2$, at the beginning or at the end, rather than the 3 places we have at later stages. Also, note that this method generalizes directly to seeking the number of towers where we change the second rule to read, "The cube immediately on top of a cube with edge-length $k$ must have edge-length at most $k + n$," where $n$ can be any fixed integer.)

Video Solution by OmegaLearn

https://youtu.be/WpSpnx8PPnc?t=732

~ pi_is_3.14

See also

2006 AIME I (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=2006_AIME_I_Problems/Problem_11&oldid=180076"