Упорядочивание

Решение

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

Пусть утверждение задачи неверно: для некоторого . Это означает, что до перестраивания по росту солдат мог стоять только перед одним из солдат . То же справедливо и для солдат , поскольку они не ниже солдата . Итак, до перестраивания шеренг солдат могли стоять только перед солдатами . Противоречие.