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