Problem:
A collection of cubes consists of one cube with edge-length for each integer . A tower is to be built using all 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 that can be constructed. What is the remainder when is divided by ?
Solution:
Let be the number of permissible towers that can be constructed from cubes, one each with edge-length for . Observe that and . For , a tower of cubes can be constructed from any tower of cubes by inserting the cube with edge-length in one of three positions: on the bottom, on top of the cube with edge-length , or on top of the cube with edge-length . Thus, from each tower of cubes, three different towers of cubes can be constructed. Also, different towers of cubes lead to different towers of cubes, and each tower of cubes becomes a permissible tower of cubes when the cube with edge-length is removed. Hence, for . Because , it follows that for . Hence , and the requested remainder is .
The problems on this page are the property of the MAA's American Mathematics Competitions