РЕШУ ОЛИМП — математика

Задания

Компьютерная сеть Пентагона представляет собой 1000 компьютеров, некоторые пары из которых соединены проводами. Хакер Вася написал вирус, который каждую минуту заражает все компьютеры, напрямую соединённые проводом с уже заражёнными. Известно, что сеть устроена таким образом, что если Вася загрузит свой вирус на любой из компьютеров, то через некоторое время заражённой окажется вся сеть. Докажите, что хакер Вася может таким образом выбрать 90 компьютеров Пентагона, что если он загрузит на них вирус одновременно, то уже через 10 минут заражённой окажется вся сеть.

Решение. Каждый компьютер представим вершиной графа, а соединение проводами ребром между ними. Из условия следует, что граф связный. Последовательность вершин, в которой всякие две соседние вершины соединены ребром, а никакое ребро не присутствует дважды, называют цепью. Цепь, которая заканчивается в той же вершине, где она началась, называют замкнутой цепью или циклом. Связный граф, в котором нет циклов, называют деревом.

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

Таким образом, перейдём к рассмотрению 1000-вершинного дерева, полученному из начального графа удалением всех циклов. Рассмотрим в этом графе цепь наибольшей длины $X минус A_1 минус A_2 минус \ldots минус A_k минус Y.$ Возможны два случая.

Если $k меньше или равно 19,$ то достаточно заразить вершину A₁₀ (или любую другую, если даже десятой нет), и через 10 минут вся сеть окажется заражённой. Действительно, так как мы выбрали цепь наибольшей длины, то в этом случае нет вершин на расстоянии больше 10 от A₁₀ (иначе можно бы было продлить путь до этой вершины до X или до Y). Поэтому этот случай тривиален.

Если $k больше или равно 20,$ то отделим от графа вершины $X, A_1, \ldots, A_10$ и всех, кто связан с ними не через A₁₁ (их не меньше 11). Среди отделённых вершин нет вершин на расстоянии больше 10 от A₁₀ (иначе, опять-таки, мы бы получили противоречие с максимальностью цепи). Значит, если мы заразим A₁₀, то вся отделённая часть окажется через 10 минут заражённой.

Заметим, что после отделения останется всё ещё дерево, так как оставшийся граф, очевидно, связен. Повторим описанную процедуру 89 раз. На каждом шаге мы либо исчерпаем компьютеры, либо отделим по крайнем мере $89 умножить на 11=979$ вершин, и останется не более 21 компьютера. Повторим для них те же самые рассуждения (но теперь заразим среднюю вершину в самом длинном пути), и получим, что мы как раз выбрали 90 компьютеров, и этого хватает.

Ключ