HMMT 二月 2007 · COMB 赛 · 第 10 题

10. [ 8 ] A subset S of the nonnegative integers is called supported if it contains 0, and k + 8 , k + 9 ∈ S for all k ∈ S. How many supported sets are there? Answer: 1430 . Note that every supported set S contains 0, 8, 9, 16, 17, 18, 24-27, 32-36, 40-45,

48-54, and all n ≥ 55 . Now define S := Z \ S, which is a subset of { 1 − 7 , 10 − 15 , 19 − 23 , 28 − 31 , 37 , 38 , 39 , 46 , 47 , 55 } satisfying the opposite property that k ∈ S = ⇒ k − 8 , k − 9 ∈ S. 55 46 47 37 38 39 28 29 30 31 19 20 21 22 23 10 11 12 13 14 15 1 2 3 4 5 6 7 ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ (0 , 0) ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ (16 , 0) Consider the above arrangement after removing the numbers not in S . The condition that S be supported ensures that sets S are in bijective correspondence with paths from (0,0) to (16,0) consisting of discrete steps of 〈 1 , 1 〉 and 〈 1 , − 1 〉 and lying above the x -axis: from the modified version of the above diagram, a unique path passes through the top items left in each column. The number of such paths is ( ) 8 · 2 1 12870 the 8th Catalan number, so the answer is C = = = 1430 . (Incidentally, 16 choose 8 was 8 8+1 8 9 computed in an earlier problem.) Without the explicit formula for Catalan numbers, the answer can be computed recursively by filling in the number of ways a path can reach (16,0) from each position in the figure. One works right to left, obtaining the following: 1 8 1 35 7 1 110 27 6 1 275 75 20 5 1 572 165 48 14 4 1 1001 297 90 28 9 3 1 1430 429 132 42 14 5 2 1 1430 429 132 42 14 5 2 1 1 2 2 One can exploit symmetry and, having determined the middle column, sum the squares: 1 + 7 + 2 2 2 20 + 28 + 14 = 1430 . 3