58-я Международная Математическая OлимпиадаБразилия, Рио-де-Жанейро, 2017 год

Дано целое число $N \ge 2$. Команда, состоящая из ${N(N + 1)}$ футболистов, любые два из которых разного роста, построена в ряд. Тренер хочет удалить из ряда ${N(N - 1)}$ игроков так, чтобы для оставшегося ряда из $2N$ игроков выполнялись следующие $N$ условий:
(1) никто не стоит между двумя самыми высокими игроками,
(2) никто не стоит между третьим и четвертым по росту игроками,
$\vdots$
$(N)$ никто не стоит между двумя самыми низкими игроками.
Докажите, что это всегда возможно.

Комментарий/решение

Решение. Разделим изначальный ряд на куски $p_1,...,p_{N}$ по $N+1$ подряд идущих футболистов. Пусть $p_i=\{a_{i1}>a_{i2}>...>a_{i(N+1)}\}.$ Создадим множество $S=\{s_1,...,s_{2N}\}.$ Теперь рассмотрим следующий процесс из $N$ шагов:

$(1)$ Выберем кусок $p_i,$ в котором $a_{i2}=\max_{j=1,...,N} a_{j2}.$

Из данного куска отметим элементы $a_{i1}>a_{i2}$ и положим их в $S:$ $s_1=a_{i1}, s_2=a_{i2}.$ Потом уберем из рассмотрения этот кусок полностью.

Для $k=2,...,N:$

$(k)$ Среди оставшихся кусков выберем кусок с $\max a_{j(k+1)}.$ Из него отметим элементы $a_{jk}>a_{j(k+1)}$ и положим их в $S:$ $s_{2k-1}=a_{jk}, s_{2k}=a_{j(k+1)}.$ Потом уберем из рассмотрения этот кусок полностью.

После окончания данного процесса получим множество $S$ состоящее из некоторых $2N$ футболистов, причем из построения следует, что

$$s_1>s_2>s_3>...>s_{2N},$$

а так же элементы $s_{2k-1},s_{2k}$ лежат в одном куске для $k=1,...,N.$ Оставив только этих футболистов легко убедится, что полученная конфигурация удовлетворяет условию задачи. $\square$