Library / Saudi Arabian Mathematical Competitions /332 of 395

Saudi Arabian Mathematical Competitions

Combinatorics Difficulty 6.7 National Olympiad Prove it Saudi Arabia

Given a set of $2^{2016}$ cards with the numbers $1, 2, \ldots, 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.

Solution

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} \leq x \leq 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} < \ldots < 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$ . $\square$

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.