Какое максимальное число гостей могло остаться?

Question

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

Дмитрий · Accepted Answer

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

അ Fail അ · Answer

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