Солдаты построены в две шеренги по n человек, так что каждый солдат из первой шеренги не выше стоящего за ним солдата из второй шеренги. В шеренгах солдат выстроили по росту. Докажите, что после этого каждый солдат из первой шеренги также будет не выше стоящего за ним солдата из второй шеренги.

Обозначим роста солдат в первой шеренге как последовательность $a_1, a_2, \dots, a_n$, а во второй — как $b_1, b_2, \dots, b_n$. По условию, изначально солдаты стоят так, что $a_i \le b_i$ для всех $i = 1, \dots, n$. После того как их перестроили по росту, в каждой шеренге роста стали упорядочены: $a'_1 \le a'_2 \le \dots \le a'_n$ и $b'_1 \le b'_2 \le \dots \le b'_n$. Нам нужно доказать, что $a'_i \le b'_i$ для всех $i = 1, \dots, n$. Допустим от противного, что утверждение неверно. Тогда найдется такой индекс $k$, что $a'_k > b'_k$. Рассмотрим множество первых $k$ солдат из первой шеренги. Их роста: $a'_1, a'_2, \dots, a'_k$. Так как эта шеренга отсортирована, все они не меньше $a'_k$, то есть $a'_i \ge a'_k > b'_k$ для любого $i \in \{1, \dots, k\}$. Аналогично, рассмотрим множество последних $n-k+1$ солдат из второй шеренги. Их роста: $b'_k, b'_{k+1}, \dots, b'_n$. Все они не меньше $b'_k$. Заметим, что мы имеем $k$ человек из первой шеренги, рост каждого из которых строго больше $b'_k$, и $n-k+1$ человек из второй шеренги, рост каждого из которых не меньше $b'_k$. Всего мы рассмотрели $k + (n - k + 1) = n + 1$ человека. Но всего во второй шеренге только $n$ человек. По принципу Дирихле (или просто подсчетом), среди этих $n+1$ мест найдутся такие пары, которые противоречат исходному условию (что в каждой паре исходно «верхний» был не выше «нижнего»). Таким образом, наше предположение неверно, и $a'_i \le b'_i$ выполняется.