1. Шеренга десятиклассников и шеренга семиклассников построены так, что перед каждым десятиклассником стоит семиклассник ниже его ростом. Докажите, что если в каждой шеренге построить школьников по росту, то и в этом случае перед каждым десятиклассником стоит семиклассник ниже его ростом.

Пусть в шеренге $$n$$ десятиклассников и $$n$$ семиклассников. Обозначим рост десятиклассников как $$d_1, d_2, ..., d_n$$, а рост семиклассников как $$s_1, s_2, ..., s_n$$. По условию, $$s_i < d_i$$ для всех $$i = 1, 2, ..., n$$.

Теперь построим обе шеренги по росту. Обозначим отсортированные росты десятиклассников как $$d'_1 \le d'_2 \le ... \le d'_n$$, а отсортированные росты семиклассников как $$s'_1 \le s'_2 \le ... \le s'_n$$.

Нам нужно доказать, что после перестроения по росту по-прежнему $$s'_i < d'_i$$ для всех $$i = 1, 2, ..., n$$.

Предположим противное: существует такой $$i$$, что $$s'_i \ge d'_i$$. Это означает, что $$i$$-й по росту семиклассник выше или равен $$i$$-му по росту десятикласснику.

Так как $$s'_i$$ является $$i$$-м по росту семиклассником, то существует хотя бы $$i$$ семиклассников, чей рост не превышает $$s'_i$$, то есть $$s'_1, s'_2, ..., s'_i \le s'_i$$. Аналогично, существует хотя бы $$n - i + 1$$ десятиклассников, чей рост не меньше $$d'_i$$, то есть $$d'_i, d'_{i+1}, ..., d'_n \ge d'_i$$.

Но по условию $$s_k < d_k$$ для каждого $$k$$. Рассмотрим $$n$$ неравенств: $$s_1 < d_1, s_2 < d_2, ..., s_n < d_n$$.

Предположим, что после сортировки $$s'_i \ge d'_i$$. Это значит, что $$i$$-й по росту семиклассник выше $$i$$-го по росту десятиклассника.

Пусть $$S$$ — множество семиклассников, а $$D$$ — множество десятиклассников. Тогда $$|S| = |D| = n$$. Пусть $$S_i$$ — множество $$i$$ самых высоких семиклассников, а $$D_i$$ — множество $$i$$ самых низких десятиклассников. Тогда $$\forall s \in S_i$$ и $$\forall d \in D_i$$ выполняется $$s'_i \ge d'_i$$ для некоторого $$i$$.

Для любого $$k$$ выполняется $$s_k < d_k$$. Значит, после перестроения по росту для любого $$i$$ должно выполняться $$s'_i < d'_i$$.

Таким образом, если в каждой шеренге построить школьников по росту, то и в этом случае перед каждым десятиклассником будет стоять семиклассник ниже его ростом.