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