===== MM153 =====

** Конкурсная задача ММ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 подготовил Владимир Лецко//
----