Задача 34989

Темы:    [ Упорядочивание по возрастанию (убыванию) ] [ Доказательство от противного ]

Сложность: 3 Классы: 6,7,8

Условие

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

Решение

Обозначим через 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. Противоречие.

Источники и прецеденты использования

web-сайт

задача