Maths Olympiad Prep

Library / /842 of 860

Combinatorics Difficulty 5.8 AIME, harder Find the answer

You start out with a big pile of 320043^{2004} cards, with the numbers 1,2,3,,320041,2,3, \ldots, 3^{2004} 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 320033^{2003} 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 320023^{2002} 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?

A number or a short expression. Spacing and $ signs are ignored.

Solution

We claim that if you have cards numbered 1,2,,32n1,2, \ldots, 3^{2 n} and perform 2n2 n successive grouping operations, then cc is a possible value for your last remaining card if and only if 3nc32n3n+13^{n} \leq c \leq 3^{2 n}-3^{n}+1 This gives 32n23n+23^{2 n}-2 \cdot 3^{n}+2 possible values of cc, for a final answer of 32004231002+23^{2004}-2 \cdot 3^{1002}+2. Indeed, notice that the last remaining card cc must have been the largest of some set of three at the (2n1)(2 n-1) th step; each of these was in turn the largest of some set of three (and so cc was the largest of some set of 9 cards) remaining at the (2n3)(2 n-3) th step; each of these was in turn the largest of some set of three (and so cc was the largest of some set of 27 ) remaining at the (2n5)(2 n-5) th step; continuing in this manner, we get that cc was the largest of some 3n3^{n} cards at the first step, so c3nc \geq 3^{n}. A similar analysis of all of the steps in which we save the smallest card gives that cc is the smallest of some set of 3n3^{n} initial cards, so c32n3n+1c \leq 3^{2 n}-3^{n}+1. To see that any cc in this interval is indeed possible, we will carry out the groupings inductively so that, after 2i2 i steps, the following condition is satisfied: if the numbers remaining are a1<a2<<a32(ni)a_{1}<a_{2}<\cdots<a_{3^{2(n-i)}}, then cc is one of these, and there are at least 3ni13^{n-i}-1 numbers smaller than cc and at least 3ni13^{n-i}-1 numbers larger than cc. This is certainly true when i=0i=0, so it suffices to show that if it holds for some i<ni<n, we can perform the grouping so that the condition will still hold for i+1i+1. Well, we first group the smallest numbers as {a1,a2,a3},{a4,a5,a6},,{a3ni5,a3ni4,a3ni3}\left\{a_{1}, a_{2}, a_{3}\right\},\left\{a_{4}, a_{5}, a_{6}\right\}, \ldots,\left\{a_{3^{n-i}-5}, a_{3^{n-i}-4}, a_{3^{n-i}-3}\right\}. We then group the remaining numbers in such a way that cc and the largest 3ni13^{n-i}-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 3ni113^{n-i-1}-1 numbers smaller than cc remaining and at least 3ni13^{n-i}-1 numbers larger than cc remaining. And for the next grouping, we similarly group the largest 3ni33^{n-i}-3 numbers into 3ni113^{n-i-1}-1 groups, and arrange the remaining numbers so that the smallest 3ni113^{n-i-1}-1 numbers and cc are all the smallest in their groups. After this round of discarding, then cc will be retained, and we will still have at least 3ni113^{n-i-1}-1 numbers larger than cc and 3ni13^{n-i-1} numbers smaller than cc. This proves the induction step, and now the solution is complete.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.