HMMT 二月 2010 · COMB 赛 · 第 4 题

HMMT February 2010 — COMB Round — Problem 4

[ 4 ] Manya has a stack of 85 = 1 + 4 + 16 + 64 blocks comprised of 4 layers (the k th layer from the top k − 1 has 4 blocks; see the diagram below). Each block rests on 4 smaller blocks, each with dimensions half those of the larger block. Laura removes blocks one at a time from this stack, removing only blocks that currently have no blocks on top of them. Find the number of ways Laura can remove precisely 5 blocks from Manya’s stack (the order in which they are removed matters).

解析

[ 4 ] Manya has a stack of 85 = 1 + 4 + 16 + 64 blocks comprised of 4 layers (the k th layer from the top k − 1 has 4 blocks; see the diagram below). Each block rests on 4 smaller blocks, each with dimensions half those of the larger block. Laura removes blocks one at a time from this stack, removing only blocks that currently have no blocks on top of them. Find the number of ways Laura can remove precisely 5 blocks from Manya’s stack (the order in which they are removed matters). 1 See http://en.wikipedia.org/wiki/Bijection . 2 The four functions are a , b , c , and d , defined as follows: a (0) = 0, a (1) = 0; b (0) = 0, b (1) = 1; c (0) = 1, c (1) = 0; d (0) = 1, d (1) = 1. Combinatorics Subject Test Answer: 3384 Each time Laura removes a block, 4 additional blocks are exposed, increasing the total number of exposed blocks by 3. She removes 5 blocks, for a total of 1 · 4 · 7 · 10 · 13 ways. However, the stack originally only has 4 layers, so we must subtract the cases where removing a block on the bottom layer does not expose any new blocks. There are 1 · 4 · 4 · 4 · 4 = 256 of these (the last factor of 4 is from the 4 blocks that we counted as being exposed, but were not actually). So our final answer is 1 · 4 · 7 · 10 · 13 − 1 · 4 · 4 · 4 · 4 = 3384.