** вечеринку пришли 100 человек. Затем те, у кого не было знакомых среди присутствующих,...

Question

На вечеринку пришли 100 человек. Затем те, у кого не было знакомых среди присутствующих, ушли. Затем те, у кого был ровно один знакомый из тех, которые остались, тоже ушли. Далее аналогично действовали те, у кого было ровно 2, 3, 4, ..., 99 знакомых среди оставшихся на тот момент. Какое наибольшее количество людей могло остаться в конце?

Answer 1

Все остаться, очевидно, не могли. Предположим, что ушел всего один человек А, у которого было k знакомых. Так как остальные остались, то у каждого из них было изначально k + 1 знакомых, а когда ушел А, осталось k знакомых среди оставшихся. Значит, все они были знакомы с А, то есть у А было 99 знакомых. Тогда у остальных было по 100 знакомых, – перебор.