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 4 of 7: Keep the repeated pair, delete the rest

Previous step Next step

S\gets S\cup\{x_q,x_p\},\quad D\gets\big([1,p]\setminus\{q,p\}\big)\cup\big(G_k\setminus\{x_q,x_p\}\big)

Detailed analysis

Put $x_q$ and $x_p$ into the surviving set $S$ , then delete every other player in the initial segment $x_1,\ldots,x_p$ together with every member of $G_k$ occurring later in the row. No player survives strictly between positions $q$ and $p$ , so $x_q$ and $x_p$ become physically adjacent among the survivors, exactly as required for the pair drawn from $G_k$ .