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 3 of 7: A first repeated block appears early

Previous step Next step

N+1>N\implies \exists\, q<p\le N+1:\ x_q,x_p\in G_k

Detailed analysis

Scan the row from left to right, position by position, and stop at the first index $p$ where the block containing $x_p$ already contains an earlier player $x_q$ with $q<p$ ; call this repeated block $G_k$ . Such a repeat must occur among the first $N+1$ positions, because there are only $N$ blocks, so by the pigeonhole principle $N+1$ scanned players cannot all lie in different blocks. Minimality of $p$ then forces every block other than $G_k$ to contribute at most $1$ player to the initial segment $x_1,\ldots,x_p$ , while $G_k$ contributes exactly $2$ players there, namely $x_q$ and $x_p$ .