IMO 2017 · Problem 5

An integer \(N \geqslant 2\) is given. A collection of \(N(N + 1)\) soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove \(N(N - 1)\) players from this row leaving a new row of \(2N\) players in which the following \(N\) conditions hold:

(1) no one stands between the two tallest players,

(2) no one stands between the third and fourth tallest players,

\[ \vdots \]

\((N)\) no one stands between the two shortest players.

Show that this is always possible.

Official text of the problem. Official problem paper (PDF)

Solution

Divide the original row into \(N\) consecutive blocks of \(N+1\) players each. We will select two players from each block, ensuring that both players in each selected pair are taller than every player in all subsequently selected pairs.

Use the following procedure. At a stage when \(r\) blocks remain, we maintain the condition that each remaining block contains at least \(r+1\) players. This holds initially, with \(r=N\).

In each remaining block, identify its second tallest player. Choose the block whose second tallest player is tallest among these \(r\) players, and let that player's height be \(h\). Permanently select the two tallest players of this block, and discard its other players. This block now leaves the procedure.

From every other remaining block, discard all players taller than \(h\). Each such block loses at most one player: its second tallest player is shorter than \(h\), by our choice of the selected block and the distinctness of all heights. Consequently, each of the \(r-1\) remaining blocks still contains at least \[ (r+1)-1=r=(r-1)+1 \] players. Thus the condition needed for the next stage is preserved. Moreover, every player remaining in these blocks is shorter than both players just selected.

The procedure therefore continues until all \(N\) blocks have supplied a pair, including the last stage \(r=1\), when the remaining block has at least two players.

Keep precisely these \(2N\) selected players. By construction, the first selected pair consists of the two tallest retained players, the second selected pair consists of the third and fourth tallest, and so on.

Finally, the two retained players from any original block are adjacent in the final row: every original player between them belongs to that same consecutive block, and all its other players have been discarded. Hence every required pair is adjacent.

The number of removed players is exactly \[ N(N+1)-2N=N(N-1), \] as required.

The solution was checked against the official IMO shortlist solutions.