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

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

Условие

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

Подсказка

Попробуйте сначала выстроить по росту рыцарей, а потом уже распределять "по росту" плащи.

Решение

Сначала каждому рыцарю его плащ был короток. Начнём одновременно выстраивать по росту рыцарей и перераспределять плащи. Поменяем плащи у самого высокого рыцаря и рыцаря, имеющего самый длинный плащ. Тогда каждому из этих рыцарей их новые плащи будут малы: первому  — потому что даже рыцарю меньшего роста этот плащ был короток; второму  — потому что ему был короток даже более длинный плащ. Теперь на самого высокого рыцаря надет самый длинный плащ. Отведём этого рыцаря в сторону. (Разумеется, если на самом высоком рыцаре был уже надет самый длинный плащ, он не будет ни с кем меняться плащами, а сразу отойдёт в сторону.) Среди оставшихся снова поменяем плащи у самого высокого рыцаря и рыцаря, имеющего самый длинный плащ; снова отведём самого высокого рыцаря в сторону. Снова всем рыцарям их плащи будут коротки. Будем повторять всё это до тех пор, пока и все рыцари, и все плащи не "выстроятся по росту". Поскольку на всех промежуточных этапах всем рыцарям были коротки их плащи, то после всех переодеваний каждому рыцарю будет короток надетый на нём плащ.

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

книга
Автор Козлова Е.Г.
Название Сказки и подсказки
задача
Номер 343

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

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