Конкурсная задача ММ153 (ТГ-2) (4 балла)

Пусть n, m и k означают соответственно число вершин, ребер и связных компонент графа. Какое наименьшее количество изолированных вершин может иметь граф, для которого выполняется соотношение 11k = 10n = 8m?

Решение

Очевидно, что условие 11k = 10n = 8m равносильно следующему: m = 55t, n = 44t, k = 40t, для некоторого натурального t.

Широко известно и легко доказывается, что при фиксированных m и k наибольшее число ребер достигается в графе, в котором все ребра сосредоточены в одной связной компоненте (если это не так, число ребер легко увеличить, перебросив вершину из одной компоненты в другую, имеющую не меньше вершин, чем исходная).
Отсюда сразу следует, что t>6 т.к. при меньших t не удается «разместить» в графе 55t ребер. При t=7 это уже возможно. Имеем m = 385, n = 308, k = 280. Если 279 компонент сделать одновершинными, то на 280-ю придется 29 вершин. Поскольку C(29,2) = 406 > 385, существует граф с 279-ю изолированными вершинами, удовлетворяющий условиям задачи.
Поскольку C(28,2) + C(2,2) = 379 < 385, уменьшить число изолированных вершин при t = 7 нельзя.

Остается показать, что при бОльших t изолированных вершин будет больше. Из соотношения 11k = 10n вытекает, что изолированные вершины составляют не менее 90% от общего числа компонент. 90% достигается в случае, когда остальные компоненты имеют по две вершины (при нашем количестве ребер это, конечно же невозможно, так что изолированных вершин будет даже более 90%). Но уже при t = 8 90% от k будет больше чем 279.

Ответ: 279.

Обсуждение

Составляя задачу, я планировал ответ 278. Еще одна компонента планировалась двухвершинной, а самая большая должна была быть 28-вершинной. Но уже после публикации задачи неожиданно выяснилось, что C(28,2) не равно 384

Награды

За правильное решение задачи ММ153 Олег Полубасов, Сергей Половинкин, Виктор Филимоненков, Дмитрий Пашуткин и Николай Дерюгин получают по 4 призовых балла. Александр Князев получает 3 призовых балла, а Алексей Волошин и Анатолий Казмерчук - по 2 призовых балла.

Эстетическая оценка - 4.5 балла

Разбор задачи ММ153 подготовил Владимир Лецко

---