2008 Mock ARML 2 Problems/Problem 6

Problem

John has a pile of blocks. On top of the pile is one block. Below this block are two smaller blocks. Below each of these two blocks are two even smaller blocks. Below each of these blocks are two still smaller blocks, and so on until the last row, which contains blocks. John removes blocks one at a time, removing only blocks that currently have no blocks on top of them. Find the number of ways (order matters) in which John can remove exactly seven blocks.

Solution

Obviously, the pile is layers. Each time we remove a brick, we add one more choice for the next one - choice for the first, for the second, etc. So if we remove the restriction of layers, we have choices. However, we must now subtract each selection of bricks which tries to grab from the th layer. To select one of these, we must always take a brick from the lowest layer possible, and there are always two possible choices. This means there are ways to try to remove a brick from the th layer or ways to remove only bricks from the first .

The pile has layers. With each block John removes, there are two more blocks that are now exposed to the top. Thus there is choice for the first block, choices for the second block, and so forth, such that there are possible ways to remove seven blocks. However, this counting includes paths that take blocks from the non-existent 7th layer. To reach this layer, each brick must be removed from the lowest layer possible, so that there are always choices. Thus, there are ways to reach the bottom layer, and the answer is .

See also

2008 Mock ARML 2 (Problems, Source)
Preceded by Problem 5	Followed by Problem 7
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8