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$