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

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

Условие

В гости пришло 10 гостей и каждый оставил в коридоре пару калош. Все пары калош имеют разные размеры. Гости начали расходиться по одному, одевая любую пару калош, в которые они могли влезть (т.е. каждый гость мог надеть пару калош, не меньшую, чем его собственные). В какой-то момент обнаружилось, что ни один из оставшихся гостей не может найти себе пару калош, чтобы уйти. Какое максимальное число гостей могло остаться?

Подсказка

Если осталось больше пяти гостей, то гость, имеющий самый маленький размер калош среди оставшихся гостей, может надеть самые большие из оставшихся калош.

Решение

Пронумеруем гостей и их пары калош числами от 1 до 10 в порядке возрастания размера калош. Предположим, что осталось 6 гостей (и соответственно 6 пар калош). Тогда наименьший номер оставшегося гостя не больше 5, а наибольший номер оставшихся пар калош не меньше 6, поэтому гость с наименьшим номером сможет надеть калоши с наибольшим номером. Противоречие. С другой стороны, если последовательно уходили гости с номерами 1, 2, 3, 4, 5, и надевали соответственно калоши с номерами 10, 9, 8, 7, 6, то ни один из оставшихся пяти гостей не сможет надеть ни одну пару оставшихся калош.

Ответ

5.00

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

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

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

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