Увидеть граф (переформулировки)

a) Наблюдение 1: не на границе испачканные клетки располагаются парами, то есть нет отдельно стоящей, иначе мы сразу сможем вырезать бублик. Сколько бубликов запрещает пара? Если испачканные клетки соседние по стороне, то они запрещают 12 бубликов, а если соседние по одной вершине, то 14 бубликов. Если одна клетка испачкана на границе, то она запрещает максимум 3 бублика. Так как центральная клетка бублика может быть внутри квадрата , то всего бубликов 4900. Но проблема в том, что клетки могут располагаются не парами, а, например, по три клетки. Для того чтобы доказать задачу формально, перейдем к графам.

Вершинами будут клетки, залитые кофе. Соединим клетки ребром, если они соседние по стороне или вершине. Рассмотрим одну компоненту связности. Пусть в нем вершин. Докажем, что они запрещают не больше чем бубликов. Заметим, что в любой компоненте связности есть такая вершина, что если ее удалить, связность сохранится. Почему это правда? Давайте выделим в графе остовное дерево. Как это сделать? Если в графе циклов нет, то он уже дерево и все хорошо, если цикл есть, то удалим одно ребро из цикла, связность не нарушится, а количество циклов в графе уменьшилось на один, так как циклов изначально было конечно, то такой операцией мы из графа выделим дерево. У дерева есть хотя бы одна вершина степени один, ее то мы и можем удалить, сохранив связность. Посмотрим на эту вершину А, она соединена хотя бы с еще одной вершиной Б. Давайте заметим, что множества бубликов, которые запрещают вершины А и Б пересекаются хотя бы по двум бубликам, поэтому количество бубликов, которые запрещает только А не больше шести. Тогда вершин в нашей компоненте запрещают не больше чем бубликов (так как мы знаем, что ). Таким образом, каждая клетка с кофе в среднем запрещает не больше 7 бубликов, значит, всего запрещено не больше , поэтому найдется бублик, который мы сможем вырезать.

b) Оставляется читателям в качестве упражнения на построение примера:)