Problem 5

An integer

N \ge 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: no one stands between the two tallest players, no one stands between the third and fourth tallest players,

\ldots

, no one stands between the two shortest players. Show that this is always possible.

Step 7 of 7: Combine the pairs and conclude

Previous step Next step

P(1)\ \wedge\ \big(P(N-1)\Rightarrow P(N)\big)\ \Longrightarrow\ P(N)\ \ \forall N\ge 1

Detailed analysis

The pair $x_q,x_p$ together with the $N-1$ pairs produced by the induction hypothesis give $N$ pairs in total. Since $G_k$ is shorter than every block among the other $N-1$ blocks that lies after it and taller than every one before it, and since the sub-row's own blocks inherit the same left-to-right height order, these $N$ pairs occupy exactly the consecutive height-ranks $(1,2),(3,4),\ldots,(2N-1,2N)$ in the final row of $2N$ survivors, and each pair is physically adjacent by construction. This completes the induction step, so the claim holds for every $N\ge 1$ , and in particular for every $N\ge 2$ as the problem requires.