HMMT 二月 2004 · 冲刺赛 · 第 34 题

HMMT February 2004 — Guts Round — Problem 34

[12] Find the number of 20-tuples of integers x , . . . , x , y , . . . , y with the following 1 10 1 10 properties: • 1 ≤ x ≤ 10 and 1 ≤ y ≤ 10 for each i ; i i • x ≤ x for i = 1 , . . . , 9; i i +1 • if x = x , then y ≤ y . i i +1 i i +1

解析

Find the number of 20-tuples of integers x , . . . , x , y , . . . , y with the following prop- 1 10 1 10 erties: • 1 ≤ x ≤ 10 and 1 ≤ y ≤ 10 for each i ; i i 10 • x ≤ x for i = 1 , . . . , 9; i i +1 • if x = x , then y ≤ y . i i +1 i i +1 ( ) 109 Solution: 10 By setting z = 10 x + y , we see that the problem is equivalent to choosing a nonde- i i i creasing sequence of numbers z , z , . . . , z from the values 11 , 12 , . . . , 110. Making a 1 2 10 further substitution by setting w = z − 11 + i , we see that the problem is equivalent to i i choosing a strictly increasing sequence of numbers w , . . . , w from among the values 1 10 ( ) 109 1 , 2 , . . . , 109. There are ways to do this. 10