2008 Mock ARML 2 Problems/Problem 6

Revision as of 09:12, 1 June 2008 by Azjps (talk | contribs) (Solution: delete typo redundancy [ARML forum is locked, credit to worthawholebean])
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

John has a pile of $63$ 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 $32$ 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 $6$ layers. With each block John removes, there are two more blocks that are now exposed to the top. Thus there is $1$ choice for the first block, $2$ choices for the second block, and so forth, such that there are $7!$ 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 $2$ choices. Thus, there are $2^6$ ways to reach the bottom layer, and the answer is $7! - 2^6 = \boxed{4976}$.

See also

2008 Mock ARML 2 (Problems, Source)
Preceded by
Problem 5
Followed by
Problem 7
1 2 3 4 5 6 7 8
Invalid username
Login to AoPS