HMMT 十一月 2010 · 冲刺赛 · 第 11 题
HMMT November 2010 — Guts Round — Problem 11
题目详情
- [ 8 ] How many nondecreasing sequences a , a , . . . , a are composed entirely of at most three dis- 1 2 10 tinct 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)?
解析
- [ 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 i the number of times i occurs in the sequence. There is a correspondence from all possible sequences b , 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. i Our goal now is to count the number of possible sequences b , b , . . . , b meeting our conditions. We 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. ( ) 9 There are = 36 ways to choose the two terms b , b ( i < j ) which are nonzero. From here, we have i j 2 9 choices for the value of b , namely 1 through 9 (since both b and b must be nonzero), and b will i i j j be fixed, so this case gives us 36 · 9 = 324 possible sequences. Case 3: The sequence has exactly three nonzero terms. ( ) 9 There are = 84 ways to choose the three terms b , b , b ( i < j < k ) which are nonzero. Letting i j k 3 Guts Round 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 ( ) 9 There are = 36 solutions to this equation (consider placing two dividers in the nine spaces between 2 the ten elements), giving 84 · 36 = 3024 possbilities in this case. We then have 9 + 324 + 3024 = 3357 possible sequences.