ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 34989
Темы:    [ Упорядочивание по возрастанию (убыванию) ]
[ Доказательство от противного ]
Сложность: 3
Классы: 6,7,8
В корзину
Прислать комментарий

Условие

Солдаты построены в две шеренги по 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. Противоречие.

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

web-сайт
задача

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .