HMMT 二月 2008 · COMB 赛 · 第 10 题
HMMT February 2008 — COMB Round — Problem 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 1
解析
- [ 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 maps k k k bijectively to the set of nonnegative integers through the map ( a , b ) 7 → a + ( k + 1) b , as a is simply k k k k k the remainder of a + ( k + 1) b upon division by k + 1. By letting x = a + ( k + 1) b , we see that k k k k k the 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 ( ) 22 bars” argument, we see that the answer is = 1540. 3 A generating functions solution is also available. It’s not hard to see that the answer is the coefficient 19 of x in ( ) ( ) ( ) 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 1 − 4 = = (1 − x ) . 4 (1 − x ) ( ) ( ) − 4 22 19 − 4 19 Using binomial theorem, we find that the coefficient of x in (1 − x ) is ( − 1) = = 1540. 19 19 4