Question

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

Answer 1

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