HMMT 二月 2005 · COMB 赛 · 第 10 题
HMMT February 2005 — COMB Round — Problem 10
题目详情
- You start out with a big pile of 3 cards, with the numbers 1 , 2 , 3 , . . . , 3 written on them. You arrange the cards into groups of three any way you like; from each group, you keep the card with the largest number and discard the other two. You now again 2003 arrange these 3 remaining cards into groups of three any way you like, and in each group, keep the card with the smallest number and discard the other two. You now 2002 have 3 cards, and you again arrange these into groups of three and keep the largest number in each group. You proceed in this manner, alternating between keeping the largest number and keeping the smallest number in each group, until you have just one card left. How many different values are possible for the number on this final card? 1
解析
- You start out with a big pile of 3 cards, with the numbers 1 , 2 , 3 , . . . , 3 written on them. You arrange the cards into groups of three any way you like; from each group, you keep the card with the largest number and discard the other two. You now again 2003 arrange these 3 remaining cards into groups of three any way you like, and in each group, keep the card with the smallest number and discard the other two. You now 2002 have 3 cards, and you again arrange these into groups of three and keep the largest number in each group. You proceed in this manner, alternating between keeping the largest number and keeping the smallest number in each group, until you have just one card left. 3 How many different values are possible for the number on this final card? 2004 1002 Solution: 3 − 2 · 3 + 2 2 n We claim that if you have cards numbered 1 , 2 , . . . , 3 and perform 2 n successive grouping operations, then c is a possible value for your last remaining card if and only if n 2 n n 3 ≤ c ≤ 3 − 3 + 1 . 2 n n 2004 1002 This gives 3 − 2 · 3 + 2 possible values of c , for a final answer of 3 − 2 · 3 + 2. Indeed, notice that the last remaining card c must have been the largest of some set of three at the (2 n − 1)th step; each of these was in turn the largest of some set of three (and so c was the largest of some set of 9 cards) remaining at the (2 n − 3)th step; each of these was in turn the largest of some set of three (and so c was the largest of some set of 27) remaining at the (2 n − 5)th step; continuing in this manner, we get that c n n was the largest of some 3 cards at the first step, so c ≥ 3 . A similar analysis of all of the steps in which we save the smallest card gives that c is the smallest of some set n 2 n n of 3 initial cards, so c ≤ 3 − 3 + 1. To see that any c in this interval is indeed possible, we will carry out the groupings inductively so that, after 2 i steps, the following condition is satisfied: if the numbers remaining are a < a < · · · < a , then c is one of these, and there are at least 2( n − i ) 1 2 3 n − i n − i 3 − 1 numbers smaller than c and at least 3 − 1 numbers larger than c . This is certainly true when i = 0, so it suffices to show that if it holds for some i < n , we can perform the grouping so that the condition will still hold for i + 1. Well, we first n − i n − i n − i group the smallest numbers as { a , a , a } , { a , a , a } , . . . , { a , a , a } . 1 2 3 4 5 6 3 − 5 3 − 4 3 − 3 n − i We then group the remaining numbers in such a way that c and the largest 3 − 1 numbers are each the largest in its respective group; it is easy to see that we can do this. After retaining the largest number in each group, we will then have at least n − i − 1 n − i 3 − 1 numbers smaller than c remaining and at least 3 − 1 numbers larger n − i than c remaining. And for the next grouping, we similarly group the largest 3 − 3 n − i − 1 numbers into 3 − 1 groups, and arrange the remaining numbers so that the smallest n − i − 1 3 − 1 numbers and c are all the smallest in their groups. After this round of n − i − 1 discarding, then c will be retained, and we will still have at least 3 − 1 numbers n − i − 1 larger than c and 3 numbers smaller than c . This proves the induction step, and now the solution is complete. 4