2006 AIME I Problems/Problem 11
Problem
A collection of 8 cubes consists of one cube with edge-length 
for each integer 
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
must have edge-length at most 
Let 
be the number of different towers than can be constructed. What is the remainder when is divided by 1000?
Solution
We proceed recursively. Suppose we can build 
towers using blocks of size 
. How many towers can we build using blocks of size 
? If we remove the block of size 
from such a tower (keeping all other blocks in order), we get a valid tower using blocks . Given a tower using blocks (with 
), we can insert the block of size in exactly 3 places: at the beginning, immediately following the block of size 
or immediately following the block of size 
. Thus, there are 3 times as many towers using blocks of size as there are towers using only . There are 2 towers which use blocks 
, so there are 
towers using blocks 
, so the answer is 
.
(Note that we cannot say, "there is one tower using the block 
, so there are 
towers using the blocks ." The reason this fails is that our recursion only worked when : when 
, there are only 2 places to insert a block of size 
, 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 must have edge-length at most 
," where 
can be any fixed integer.)
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. 
