|
|
 |
Условие
На вечеринку пришли 100 человек. Затем те, у кого не было знакомых среди
пришедших, ушли. Затем те, у кого был ровно один знакомый среди оставшихся, тоже ушли. Затем аналогично поступали те, у кого было ровно 2, 3, 4, ..., 99 знакомых среди оставшихся к моменту их ухода.
Какое наибольшее число людей могло остаться в конце?
Решение
Нетрудно проверить, что если все пришедшие, кроме двух человек A и B, были знакомы между собой, то в конце должны были остаться все, кроме A и B, то есть 98 человек.
Докажем, что не могло остаться 99 человек. Ясно, что человек A, имевший изначально меньше всех знакомых (k), в некоторый момент уйдёт. Если больше никто не ушёл, то все остальные (кроме A) имели больше k знакомых до ухода A и меньше k + 1 после
его ухода. Но тогда A должен быть знаком со всеми остальными, то есть k = 99, что противоречит строгой минимальности k.
Ответ
98 человек.
