You start out with a big pile of cards, with the numbers 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 arrange these 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 have 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?
Solution
We claim that if you have cards numbered and perform successive grouping operations, then is a possible value for your last remaining card if and only if This gives possible values of , for a final answer of . Indeed, notice that the last remaining card must have been the largest of some set of three at the th step; each of these was in turn the largest of some set of three (and so was the largest of some set of 9 cards) remaining at the th step; each of these was in turn the largest of some set of three (and so was the largest of some set of 27 ) remaining at the th step; continuing in this manner, we get that was the largest of some cards at the first step, so . A similar analysis of all of the steps in which we save the smallest card gives that is the smallest of some set of initial cards, so . To see that any in this interval is indeed possible, we will carry out the groupings inductively so that, after steps, the following condition is satisfied: if the numbers remaining are , then is one of these, and there are at least numbers smaller than and at least numbers larger than . This is certainly true when , so it suffices to show that if it holds for some , we can perform the grouping so that the condition will still hold for . Well, we first group the smallest numbers as . We then group the remaining numbers in such a way that and the largest 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 numbers smaller than remaining and at least numbers larger than remaining. And for the next grouping, we similarly group the largest numbers into groups, and arrange the remaining numbers so that the smallest numbers and are all the smallest in their groups. After this round of discarding, then will be retained, and we will still have at least numbers larger than and numbers smaller than . This proves the induction step, and now the solution is complete.