HMMT 二月 2010 · COMB 赛 · 第 4 题

英文解析

4. [ 4 ] Manya has a stack of 85 = 1 + 4 + 16 + 64 blocks comprised of 4 layers (the k th layer from the topk − 1
   has 4 blocks; see the diagram below). Each block rests on 4 smaller blocks, each with dimensionshalf those of the larger block. Laura removes blocks one at a time from this stack, removing only blocksthat 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).
   See http://en.wikipedia.org/wiki/Bijection .1
   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,2
   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 thebottom 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 answeris 1 · 4 · 7 · 10 · 13 − 1 · 4 · 4 · 4 · 4 = 3384.