|
||||||||||||||||||
|
СодержаниеMM153Конкурсная задача ММ153 (ТГ-2) (4 балла) Пусть n, m и k означают соответственно число вершин, ребер и связных компонент графа. Какое наименьшее количество изолированных вершин может иметь граф, для которого выполняется соотношение 11k = 10n = 8m? Решение Очевидно, что условие 11k = 10n = 8m равносильно следующему: m = 55t, n = 44t, k = 40t, для некоторого натурального t.
Широко известно и легко доказывается, что при фиксированных m и k наибольшее число ребер достигается в графе, в котором все ребра сосредоточены в одной связной компоненте (если это не так, число ребер легко увеличить, перебросив вершину из одной компоненты в другую, имеющую не меньше вершин, чем исходная). Остается показать, что при бОльших 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 подготовил Владимир Лецко
|
|||||||||||||||||
|
||||||||||||||||||
|