HMMT 二月 2008 · COMB 赛 · 第 10 题

英文解析

10. [ 7 ] Determine the number of 8-tuples of nonnegative integers ( a , a , a , a , b , b , b , b ) satisfying 0 ≤
    1 2 3 4 1 2 3 4
    a ≤ k , for each k = 1 , 2 , 3 , 4, and a + a + a + a + 2 b + 3 b + 4 b + 5 b = 19.
    k 1 2 3 4 1 2 3 4
    Answer: 1540 For each k = 1 , 2 , 3 , 4, note that set of pairs ( a , b ) with 0 ≤ a ≤ k mapsk k kbijectively to the set of nonnegative integers through the map ( a , b ) 7 → a + ( k + 1) b , as a is simplyk k k k kthe remainder of a + ( k + 1) b upon division by k + 1. By letting x = a + ( k + 1) b , we see thatk k k k kthe problem is equivalent to finding the number of quadruples of nonnegative integers ( x , x , x , x )
    1 2 3 4
    such that x + x + x + x = 19. This is the same as finding the number of quadruples of positive
    1 2 3 4
    integers ( x + 1 , x + 1 , x + 1 , x + 1) such that x + x + x + x = 23. By a standard “dots and
    1 2 3 4 1 2 3 4
    ( )
    bars” argument, we see that the answer is = 1540.22
    A generating functions solution is also available. It’s not hard to see that the answer is the coefficient 3
    of x in 19
    ( ) ( ) ( )
    2 2 3 2 3 4
    (1 + x ) 1 + x + x 1 + x + x + x 1 + x + x + x + x
    ( ) ( ) ( ) ( )
    2 4 3 6 4 8 5 10
    1 + x + x + · · · 1 + x + x + · · · 1 + x + x + · · · 1 + x + x + · · ·
    ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
    2 3 4 5
    1 − x 1 − x 1 − x 1 − x 1 1 1 1
    2 3 4 5=
    1 − x 1 − x 1 − x 1 − x 1 − x 1 − x 1 − x 1 − x − 41 = = (1 − x ) .
    (1 − x )4
    ( ) ( ) − 4 22
    19 − 4 19
    Using binomial theorem, we find that the coefficient of x in (1 − x ) is ( − 1) = = 1540.
    19 19 4