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 forall 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.
    46 4755
    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 besupported ensures that sets S are in bijective correspondence with paths from (0,0) to (16,0) consistingof discrete steps of 〈 1 , 1 〉 and 〈 1 , − 1 〉 and lying above the x -axis: from the modified version of the abovediagram, a unique path passes through the top items left in each column. The number of such paths is
    ( )
    8 · 2
    1 12870
    the 8 th Catalan number, so the answer is C = = = 1430 . (Incidentally, 16 choose 8 was
    8+1 8 98
    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 positionin the figure. One works right to left, obtaining the following:
    8 11
    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