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

英文解析

34. 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
    • x ≤ x for i = 1 , . . . , 9;10
    i i +1
    • if x = x , then y ≤ y .
    i i +1 i i +1
    ( )
    Solution:109
    By setting z = 10 x + y , we see that the problem is equivalent to choosing a nonde-10
    i i icreasing 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 toi ichoosing a strictly increasing sequence of numbers w , . . . , w from among the values
    1 10
    ( )
    1 , 2 , . . . , 109. There are ways to do this.109
    10