Задача 068 — Задачи на Графы

В комнате находятся 99 человек. Каждую минуту из комнаты выходит человек, у которого количество знакомых среди присутствующих хотя бы на 2 больше, чем у каждого из остальных. Через несколько минут такого человека не нашлось. Какое минимальное количество людей могло остаться к этому моменту в комнате? (Знакомства взаимные.)

Подсказка

Выкидывание вершины с рёбрами не увеличивает степени остальных, потому степень каждого следующего выходящего (на момент выхода) хотя бы на 2 меньше предыдущей.

Решение

Ответ. 51 человек.

Решение: Оценка. Рассмотрим граф с 99 вершинами, рёбра соответствуют знакомствам. Выкидывание вершины с рёбрами не увеличивает степени остальных, потому степень каждого следующего выходящего (на момент выхода) хотя бы на 2 меньше предыдущей. Поэтому их степени не больше $98,96, \ldots 4,2$ соответственно. Но удалить вершину степени 2 невозможно, так как есть ещё ненулевые степени, а вершины степени 1 и 0 не подходят по условию. Таким образом, из комнаты выйдет не более 48 человек.

Пример. Пусть человек с номером $1 \leqslant k \leqslant 48$ знаком с людьми с номерами от $2 k+1$ до 99, других знакомств нет. Уходить они будут по порядку от 1 до 48 . На момент ухода $k$ -го человека: ему не знакомы только $k$ следующих за ним, остальным из этих 48 — хотя бы $k+1$ следующих и предыдущий, а последним 51 — хотя бы 50 , что тоже не меньше $k+2$ .