HMMT 二月 2005 · COMB 赛 · 第 10 题

英文解析

10. You start out with a big pile of 3 cards, with the numbers 1 , 2 , 3 , . . . , 3 writtenon 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 eachgroup, 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 largestnumber in each group. You proceed in this manner, alternating between keeping thelargest number and keeping the smallest number in each group, until you have just onecard left.
    How many different values are possible for the number on this final card?3
    2004 1002
    Solution: 3 − 2 · 3 + 2
    2 n
    We claim that if you have cards numbered 1 , 2 , . . . , 3 and perform 2 n successivegrouping operations, then c is a possible value for your last remaining card if and onlyn 2 n nif
    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 ofthree 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; eachof these was in turn the largest of some set of three (and so c was the largest of someset of 27) remaining at the (2 n − 5)th step; continuing in this manner, we get that cn nwas the largest of some 3 cards at the first step, so c ≥ 3 . A similar analysis of allof the steps in which we save the smallest card gives that c is the smallest of some setn 2 n nof 3 initial cards, so c ≤ 3 − 3 + 1.
    To see that any c in this interval is indeed possible, we will carry out the groupingsinductively so that, after 2 i steps, the following condition is satisfied: if the numbersremaining are a < a < · · · < a , then c is one of these, and there are at least
    2( n − i )
    1 2
    n − i n − i 3
    3 − 1 numbers smaller than c and at least 3 − 1 numbers larger than c . This iscertainly true when i = 0, so it suffices to show that if it holds for some i < n , wecan perform the grouping so that the condition will still hold for i + 1. Well, we firstn − i n − i n − igroup 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 dothis. After retaining the largest number in each group, we will then have at leastn − i − 1 n − i
    3 − 1 numbers smaller than c remaining and at least 3 − 1 numbers largern − ithan 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 smallestn − i − 1
    3 − 1 numbers and c are all the smallest in their groups. After this round ofn − i − 1
    discarding, then c will be retained, and we will still have at least 3 − 1 numbersn − i − 1
    larger than c and 3 numbers smaller than c . This proves the induction step, andnow the solution is complete. 4