Солдаты построены в две шеренги по n человек, так что каждый солдат из первой шеренги не выше стоящего за ним солдата из второй шеренги. В шеренгах солдат выстроили по росту. Докажите, что после этого каждый солдат из первой шеренги также будет не выше стоящего за ним солдата из второй шеренги. 
Обозначим через a1, a2, ..., an рост солдат первой шеренги в порядке убывания, а через b1, b2, ..., bn рост солдат второй шеренги в порядке убывания (те же обозначения используем и для самих солдат). Пусть утверждение задачи неверно:  ak > bk  для некоторого k. Это означает, что до перестраивания по росту солдат ak мог стоять только перед одним из  k – 1  солдат b1, b2, ..., bk–1. То же справедливо и для солдат a1, a2, ..., ak–1, поскольку они не ниже солдата ak. Итак, до перестраивания шеренг k солдат a1, a2, ..., ak могли стоять только перед  k – 1  солдатами b1, b2, ..., bk–1. Противоречие. 
Упорядочивание по возрастанию (убыванию) Доказательство от противного