SAUDI ARABIAN MATHEMATICAL COMPETITIONS

Question

Given a set of 2^2016 cards with the numbers 1, 2, , 2^2016 written on them. We divide the set of cards into pairs arbitrarily; from each pair, we keep the card with larger number and discard the other. We now again divide the 2^2015 remaining cards into pairs arbitrarily; from each pair, we keep the card with smaller number and discard the other. We now have 2^2014 cards, and again divide these cards into pairs and keep the larger one in each pair. We keep doing this way, alternating between keeping the larger number and keeping the smaller number in each pair, until we have just one card left. Find all possible values of this final card.

Accepted Answer

Note that the remaining number is kept 1008 times as the larger one of the pair. So it is bigger than at least 2^1008-1 numbers. Similarly, the remaining number is kept 1008 times as the smaller one of the pair so it is smaller than at least 2^1008-1 numbers. Therefore, the remaining number x satisfies 2^1008 x 2^2016 - 2^1008 + 1. To prove that any x satisfies the above inequalities is true, we can carry out the pairing inductively so that after 2i steps, the following condition is satisfied: if the numbers remaining are a_1 < a_2 < < a_2^2(n-i) then x is one of these, and there are at least 2^n-i-1 numbers smaller than x and at least 2^n-i-1 numbers larger than x.