Решение задачи 286

Условие:

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

Решение:

Представим эту задачу в виде графа, где люди это вершины, а ребро между вершинами означает то, что соответствующие люди знакомы. Когда человек уходит, будем удалять соответствующую ему вершину и все выходящие из нее ребра. Определим k-ый шаг: момент, когда уходят те, у кого ровно k друзей из оставшихся.

Покажем, что хотя бы один человек уйдет. Действительно, рассмотрим вершину с минимальной степенью (их может быть несколько), допустим эта степень равна k. Тогда на k-ом шаге мы удалим эту вершину.

Покажем, что двое точно уйдут. От противного, предположим, что ушел только один человек. Степень соответствующей ему вершины равна k. Тогда у всех остальных вершин степень строго больше k. Но после удаления вершины, степень всех остальных должна была стать k, т.к. больше никто не ушел. Получается, что ушедший человек знаком со всеми, и степень его вершины изначально равна 99, а у всех остальных -- 100, чего не может быть, противоречие.

Приведем пример в котором остались 98 человек (ушли только двое). Рассмотрим такой граф: K₉₈ -- полный граф на 98 вершинах, еще две вершины A, B, соединенные со всеми вершинами из K₉₈, но не между собой.

У вершин A и B степени равны 98, а у всех вершин из K₉₈ степени равны 99. Тогда на 98-ом шаге уйдут вершины A и B, и у всех оставшихся вершин степени будут равны 97, то есть больше никто не уйдет.

Ответ: 98.