IMO 2017 Problem 5

I didn't solve this one. It's very easy to get wrong with this problem: I did it once in 2017 and thought I solved it, then read the solution to find out I didn't. Now that I already forget the solution, same thing happens again!

================================

For any positive integer $N$, you are given $N(N+1)$ distinct numbers in a row. Prove that we can always remove $N(N-1)$ of them so that among the remaining $2N$ numbers, the largest and the second largest are adjacent, the third largest and the fourth largest are adjacent, and so on.

================================

Proof:

Divide the numbers into $N$ blocks of $N+1$ numbers. In round $i=0,1,\ldots,N-1$ the following happens.

Initially we have $N-i$ blocks of $N+1-i$ numbers. We then sequentially pick out the largest among them until two numbers from the same block is picked. This is guaranteed to happen before we pick the $(N+2-i)$-th number because there are only $N-i$ blocks.

The two picked numbers from the same block go into a pool $P$ that will eventually consist of the $2N$ numbers asked for. The rest of that block is discarded, so are all other picked numbers. Finally, for any block that hasn't been touched in this round, discard a random number. This concludes round $i$.

Clearly before round $i+1$, we have $N-i-1$ blocks of $N-i$ numbers. Moreover by the end of round $N-1$, pool $P$ has the $2N$ numbers satisfying the desired properties.

Q.E.D.