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 2 of 7: Split the row into height-blocks

Previous step Next step

G_1<G_2<\cdots<G_N,\qquad |G_j|=N+1

Detailed analysis

List the players in position order as $x_1,\ldots,x_{N(N+1)}$ and give each one its overall height rank. Split them by height alone into $N$ consecutive blocks $G_1,\ldots,G_N$ , each of size $N+1$ , so that every member of $G_j$ is shorter than every member of $G_{j+1}$ . If the final $2N$ survivors contain exactly $2$ members of each block, those pairs automatically occupy the required consecutive height-ranks $(2j-1,2j)$ in block order.