Обозначим через a₁, a₂, ..., a_n рост солдат первой шеренги в порядке убывания, а через b₁, b₂, ..., b_n рост солдат второй шеренги в порядке убывания (те же обозначения используем и для самих солдат). Пусть утверждение задачи неверно:  a_k > b_k  для некоторого k. Это означает, что до перестраивания по росту солдат a_k мог стоять только перед одним из  k – 1  солдат b₁, b₂, ..., b_k–1. То же справедливо и для солдат a₁, a₂, ..., a_k–1, поскольку они не ниже солдата a_k. Итак, до перестраивания шеренг k солдат a₁, a₂, ..., a_k могли стоять только перед  k – 1  солдатами b₁, b₂, ..., b_k–1. Противоречие.

Ответ задачи отсутствует