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 1 of 7: Reduce the problem to an induction on

N

Previous step Next step

In plain words

Since removing players is monotone, the natural strategy is to peel off one adjacent pair at a time and recurse on a smaller version of exactly the same problem.

N(N+1)=2N+N(N-1)

Detailed analysis

We prove by strong induction on $N$ that for every integer $N\ge 1$ , a row of $N(N+1)$ players of distinct heights admits $N(N-1)$ deletions leaving $2N$ survivors whose consecutive height-ranks $(2k-1,2k)$ for $k=1,\ldots,N$ are each physically adjacent in the resulting row; the problem's requested range $N\ge 2$ is included as a special case. The base case $N=1$ needs no deletions at all: there are only $2$ players, so the single required pair is trivially adjacent.