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

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