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 5 of 7: Each surviving block still has enough players

Previous step Next step

\forall j\neq k:\ N\le \big|G_j\cap(p,N(N+1)]\big|\le N+1

Detailed analysis

Because at most $1$ member of any block other than $G_k$ appeared in the deleted prefix $x_1,\ldots,x_p$ , each block $G_j$ with $j\neq k$ still has at least $N$ of its $N+1$ members among the undeleted players to the right of position $p$ . Discard, if necessary, one extra survivor from any block that still has $N+1$ members left, so that every one of the $N-1$ remaining blocks is trimmed to exactly $N$ players, giving a pool of exactly $(N-1)N$ players in total.