HMMT 十一月 2010 · 冲刺赛 · 第 11 题

英文解析

11. [ 8 ] How many nondecreasing sequences a , a , . . . , a are composed entirely of at most three distinct
    1 2 10
    numbers from the set { 1 , 2 , . . . , 9 } (so 1 , 1 , 1 , 2 , 2 , 2 , 3 , 3 , 3 , 3 and 2 , 2 , 2 , 2 , 5 , 5 , 5 , 5 , 5 , 5 are both allowed)?
    Answer: 3357 From any sequence a , a , . . . , a , construct a sequence b , b , . . . , b , where b counts
    1 2 10 1 2 9 ithe number of times i occurs in the sequence. There is a correspondence from all possible sequencesb , b , . . . , b with at most 3 nonzero terms which add to 10, since any sequence of a , a , . . . , a will
    1 2 9 1 2 10
    be converted to this form, and from any sequence b , b , . . . , b , we can construct a unique sequence of
    1 2 9
    a -s by listing i b times (for 1 ≤ i ≤ 9) in nondecreasing order.
    Our goal now is to count the number of possible sequences b , b , . . . , b meeting our conditions. Wei
    1 2 9
    casework on the number of nonzero terms in the sequence:
    Case 1: The sequence has exactly one nonzero term.
    Then exactly one of b , b , . . . , b is equal to 10, and all the rest are equal to 0. This gives us 9 possible
    1 2 9
    sequences in this case.
    Case 2: The sequence has exactly two nonzero terms.
    ( )
    There are = 36 ways to choose the two terms b , b ( i < j ) which are nonzero. From here, we have 9
    i j
    9 choices for the value of b , namely 1 through 9 (since both b and b must be nonzero), and b will 2
    i i j jbe fixed, so this case gives us 36 · 9 = 324 possible sequences.
    Case 3: The sequence has exactly three nonzero terms.
    ( )
    There are = 84 ways to choose the three terms b , b , b ( i < j < k ) which are nonzero. Letting 9
    i j k
    Guts Round 3
    c = b − 1 , c = b − 1 , c = b − 1, we have that c , c , c are nonnegative integers which sum to 7.
    i i j j k k i j k
    ( )
    There are = 36 solutions to this equation (consider placing two dividers in the nine spaces between 9
    the ten elements), giving 84 · 36 = 3024 possbilities in this case.2
    We then have 9 + 324 + 3024 = 3357 possible sequences.