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 6 of 7: Recurse on a smaller instance for

N-1

Previous step Next step

(N-1)N=(N-1)\big((N-1)+1\big)

Detailed analysis

The trimmed pool is again a row of distinct-height players in their original left-to-right order, split by height into $N-1$ consecutive blocks of exactly $N$ players each — precisely the shape required for parameter $N-1$ , since $(N-1)N=(N-1)\big((N-1)+1\big)$ . The induction hypothesis therefore applies to this sub-row and produces $2(N-1)$ further survivors, exactly $2$ from each of the $N-1$ blocks, arranged into $N-1$ pairs that are each physically adjacent within the sub-row and occupy consecutive height-ranks inside it.