Puzzle #49. Калоши

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

Спустя какое то время выяснилось, что ни один из оставшихся гостей не может найти себе пару калош, чтобы уйти. Какое максимальное число гостей могло остаться?

Разбор

Пронумеруем гостей и их пары калош числами от 1 до 10 в порядке возрастания размера калош.

Предположим, что осталось 6 гостей (и соответственно 6 пар калош). Тогда наименьший номер оставшегося гостя не больше 5, а наибольший номер оставшихся пар калош не меньше 6, поэтому гость с наименьшим номером сможет надеть калоши с наибольшим номером. Противоречие.

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

Ответ: 5.