Клетчатые задачи → .04 Увидеть граф (переформулировки)

Построим двудольный граф, каждому столбцу поставим в соответствие вершину левой доли, а каждой строке — правой. Для каждой отмеченной клетки, которая стоит на пересечение строки и столбца проведем ребро, между соответствующими им вершинами. Поскольку, начав с отмеченной клетки любого столбца, можно перейти к отмеченной клетке любого другого столбца, построенный граф связен. Для доказательства достаточно показать, что ребра построенного графа можно покрасить в черный цвет таким образом, чтобы для каждой вершины количество инцидентных ей черных ребер была нечетно.

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

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Ребра любого дерева, содержащего четное число вершин, можно покрасить в черный цвет так, чтобы для каждой вершины количество инцидентных ей черных ребер была нечетно.

Доказательство. Выберем произвольную вершину дерева и подвесим граф за нее. На шаге нашего алгоритма для каждой вершины -того с конца ранга будем красить инцидентное ей ребро в вершину высшего ранга в черный цвет, если число инцидентных ей черных ребер на данный момент четно. Так мы сможем сделать до тех пор, пока не дойдем до корня дерева. Оно уже будет удовлетворять требуемым условиям, поскольку для графа на черных ребрах выполнена лемма о рукопожатиях.

Рассмотрим граф, вершинами которого являются вершины прямоугольников, и две вершины графа соединены ребром тогда и только тогда, когда они являются диагонально-противоположными вершинами одного из прямоугольников разбиения.

Из условия задачи вытекает, что степень каждой вершины графа — или При этом вершин степени — четыре штуки, это и поэтому наш граф представляет собой объединение путей и циклов, причём путей в нем ровно Кроме того, все циклы имеют чётную длину, так как по условию цвета вершин в циклах чередуются. Поскольку общее число ребер графа чётно (оно равно удвоенному числу прямоугольников разбиения), и в каждом цикле чётное число ребер, то в двух путях в сумме чётное число ребер. В двух путях цвета вершин тоже чередуются.

Есть две возможности.

Два пути — это и По условию один из этих путей имеет нечётное число ребер, поэтому второй — тоже. Это и требовалось доказать.

Два пути — это и (и аналогичный случай и По условию и имеют одинаковые цвета, поэтому другие концы путей (то есть и одинаковой чётности тоже имеют одинаковые цвета.

Первое решение.

Заметим, что частным случаем разбиений является ситуация, когда каждая из Петиных и Васиных групп содержит в точности две клетки. С другой стороны, любое разбиение на группы из четного числа клеток можно измельчить на группы из двух клеток, и если существует требуемая раскраска для измельченных разбиений, то та же самая раскраска, очевидно, решает задачу и для исходных разбиений.

Теперь каждую Васину группу (из двух клеток), совпадающую с какой-то из Петиных групп, покрасим в черный и белый цвет любым из двух способов - одну клетку в черный, другую в белый цвет.

Осталось раскрасить множество клеток, которое Васей и Петей разбито на пары так что ни одна Васина пара не совпадает с Петиной парой.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Для удобства назовём непересекающиеся группы клеток одного разбиения (Пети или Васи) фигурками.

Построим вспомогательный двудольный граф G. Для каждой из фигурок одного из разбиений (Пети или Васи) добавим в граф новую, соответствующую этой фигурке вершину. При этом вершины, соответствующие фигуркам Пети, отнесём к первой доле, а вершины, соответствующие фигуркам Васи, - ко второй. Далее проведём рёбра между некоторыми вершинами графа по следующему правилу: если фигурка Пети пересекается с фигуркой Васи по нечётному количеству клеток, то проведём между соответствующими этим фигуркам вершинами ребро.

Заметим, что в построенном графе степень каждой вершины чётна. Действительно, выберем, например, произвольную фигурку Васи . Поскольку состоит из чётного числа клеток и пересекается лишь с фигурками из разбиения Пети, то по нечётному количеству клеток она будет пересекаться с чётным количеством фигурок.

Рассмотрим произвольную компоненту связности . Поскольку степень каждой вершины этой компоненты чётна, то существует цикл (т.н. эйлеров цикл), проходящий по всем рёбрам этой компоненты ровно по 1 разу. Выберем такие циклы для каждой компоненты связности . Для удобства назовём полученное разбиение рёбер графа на циклы .

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

Докажем, что полученная покраска будет искомой. Рассмотрим, например, произвольную фигурку Пети . Пусть - произвольная фигурка Васи. Заметим, что среди общих клеток фигурок и разность числа чёрных и белых клеток равна или 0 , в зависимости от чётности числа клеток в этом пересечении. Поэтому достаточно доказать, что разность +1 встречается среди пересечений фигурки Пети с фигурками Васи столько же раз, сколько и разность -1 . Пусть фигурке в графе соответствует вершина , которая лежит в некотором цикле из построенного ранее разбиения . Тогда каждой разности +1 соответствует ребро цикла , входящее в , а каждой разности -1 - ребро цикла , исходящее из . Из построения цикла следует, что рёбер, входящих в , в нём будет столько же, сколько и рёбер, исходящих из . Поэтому фигурок Васи, в клетках пересечения с которыми будет ровно на одну чёрную клетку больше, будет столько же, сколько фигурок Васи, в клетках пересечения с которыми будет ровно на одну белую клетку больше. Таким образом, в фигурке поровну чёрных и белых клеток.

Пронумеруем столбцы прямоугольника слева направо, начиная с 1.

Заметим, что белый конь ходит только по нечётным столбцам и он будет оказываться в верхней клетке тогда и только тогда, когда номер столбца даёт остаток 1 при делении на 4, а в нижней — остаток 3. Но чёрный конь ходит по такому же принципу, как и белый, следовательно, наступит момент, когда белый конь находится в нижней клетке столбца, а чёрный конь — в верхней клетке столбца, и тогда кони не смогут сделать ходы, значит, они не смогут поменяться местами.

Положим и пусть и — количества синих и красных клеток. Оценим сверху количество общих сторон красных клеток с синими.

Всего у красных клеток сторон, откуда Вдоль краёв таблицы стоит не меньше сторон красных клеток, поэтому Теперь рассмотрим граф, вершины которого — красные клетки, а рёбра соединяют клетки, имеющие общую сторону. По условию граф связен, поэтому количество его рёбер не меньше Каждому из них отвечает общая сторона двух красных клеток, засчитанная в величине два раза, поэтому из можно вычесть Получаем

(1)

Оценим теперь снизу. Сложив количества сторон всех синих клеток, получим Ясно, что на одной стороне таблицы не больше сторон синих клеток. Поэтому

(2)

Из (1) и (2) следует, что

Поскольку получаем отсюда

Поскольку а целое, получаем нужный результат.

Пронумеруем строки сверху вниз, а столбцы слева направо числами Построим ориентированный граф, вершинами которого будут клетки доски. Будем проводить ребро из клетки в клетку если жук переполз из клетки в клетку По условию из каждой вершины построенного графа выходит ровно ребро, и в каждую вершину графа входит ровно ребро. Значит, граф разбивается на циклы (некоторые циклы могут быть длины Рассмотрим один из таких циклов. Заметим, что он поровну раз переходит из строчки в строчку и обратно. Значит, и всего ребер из строки в строку и обратно будет поровну. В частности, количество жуков, сдвинувшихся влево, равно количеству жуков, сдвинувшихся вправо. Аналогичные рассуждения можно провести и со столбцами. Обозначим количество жуков, сдвинувшихся влево через количество жуков, сдвинувшихся вправо — через Понятно, что Заметим, что расстояние между жуками, сдвинувшимися в одном направлении, не изменилось. Тогда имеем хотя бы

пар жуков, расстояние между которыми не изменилось.

Первое решение.

Сопоставим многоугольнику граф: вершины - клетки, ребра будем проводить между соседними клетками. У каждой клетки 4 стороны, но стороны, которые соприкасаются с соседними клетками в многоугольнике, не учитываются в периметре. Значит, не учитываются те и только те стороны клеток, которым соответствуют ребра в графе (две стороны между соседними клетками соответствуют одному ребру). Граф на вершинах связен (так как у нас связная фигура), следовательно, ребер в нем хотя бы Значит, периметр многоугольника не больше Такой периметр достигается в прямоугольнике

Второе решение.

Оценку можно доказать по-другому. По формуле Пика площадь многоугольника равна , где количество узлов сетки внутри многоугольника, количество узлов сетки на его границе. Поскольку контур многоугольника идет по линиям сетки, то его периметр равен количеству узлов сетки, то есть . Поскольку , то

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

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

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

Нетрудно построить цикл, проходящий по разу через все клетки доски так, что соседние клетки в нем имеют общую сторону: можно, например, пройти всю первую вертикаль от нижней клетки до верхней, потом ходить по вертикалям “змейкой” от верхней горизонтали до второй снизу и обратно, а по последней вертикали вернуться на первую горизонталь и по ней — в исходную клетку. “Расклеим” все общие стороны клеток на доске, кроме общих сторон между соседними клетками нашего цикла. Даже после этого выброшенных клеток будут разбивать этот цикл не более чем на частей, а при обратной склейке цикла в доску число частей не увеличится.

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

Посчитаем общее количество ребер во введенном графе. Это количество перегородок между клетками; вертикальных перегородок и столько же горизонтальных, поэтому ребер в графе

Так как при выставлении одной фишки мы должны удалить хотя бы два ребра, то количество выставленных на доску фишек не превосходит то есть

Пример. Назовем диагональ доски, идущую из левого верхнего угла в правый нижний, главной. Будем выставлять фишки диагоналями, идя от диагонали, состоящей из одной клетки, к главной. На очередную диагональ фишки можно выставлять в любом порядке. Главную диагональ при этом не заполняем.

Предположим, мы смогли выставить 37 фишек. Когда мы выставляем фишку в некоторую клетку, у этой клетки есть как минимум 3 соседних клетки без фишек. Закрасим все границы между этими клетками в зелёный цвет (по-другому, можно ввести вспомогательный граф и посчитать его ребра).

Таким образом, каждый раз мы закрашиваем хотя бы 3 отрезка. А после выставления 37 фишек мы закрасим зелёным как минимум 111 отрезков.

Заметим, что каждый отрезок границ между клетками покрашен не более, чем единожды, а так как этих отрезков всего , то не покрашен всего лишь один отрезок.

Далее, в угловых клетках фишка не может появиться, потому что у них всего два соседа. Любая неугловая фишка, примыкающая к стороне квадрата, имеет всего три соседа, поэтому когда в ней появляется фишка, все её соседи свободны. В частности, отсюда следует, что фишки не могут появиться в двух соседних клетках на границе.

Таким образом, у каждой стороны квадрата будет не больше трёх клеток с фишками. Поэтому будет закрашено зелёным не более 6 из 7 отрезков границ в этой линии, то есть непокрашенных отрезков хотя бы 4, что противоречит выводу из пункта 2. Значит, 37 фишек выставить нельзя.

36 фишек выставить можно (числами обозначено, в какой последовательности выставляются фишки):

Для построения примера разделяющего множества, в котором не более чем клеток, раскрасим все клетки в три цвета по диагоналям: первую диагональ - в первый цвет, вторую - во второй, третью - в третий, четвертую - опять в первый, и так далее.

Любой цикл из клеток, как легко видеть, пересекает как минимум три соседних диагонали и, следовательно, содержит клетки всех трех цветов. Клеток одного из цветов будет не более , и этот цвет можно использовать в качестве разделяющего множества.

Оценка. Покажем, что никакое не подходит.

Для этого построим граф, вершинами которого являются клетки. Две клетки соединим ребром, если они являются соседними. Получим граф, в котором вершин и ребер, при этом циклы задачи находятся во взаимно однозначном соответствии с циклами в графе. Требуется удалить несколько вершин так, чтобы в оставшемся графе не было циклов.

Предположим, мы удалили вершин. Если в оставшемся графе нет циклов, то этот граф является объединением деревьев и в нем не более чем ребро. При этом из каждой удаленной вершины выходило не более 4 ребер, и всего было удалено было не более ребер. Таким образом, имеем неравенство

откуда

что невозможно при и достаточно большом .

Соединим самую верхнюю зеленую клетку на диагонали с самой нижней синей, двигаясь вниз по вертикали до горизонтали, где стоит эта синяя клетка, а потом вправо по горизонтали. То же проделаем со второй сверху зеленой и второй снизу синей диагональными клетками и т.д., доколе возможно. Когда станет невозможно, все оставшиеся на диагонали зеленые клетки будут ниже всех оставшихся синих. Соединим самую нижнюю из оставшихся зеленых клеток с самой верхней из оставшихся синих, двигаясь вверх по вертикали до горизонтали, где стоит эта синяя клетка, а потом — влево по горизонтали. То же проделаем со второй снизу из оставшихся зеленых и второй снизу из оставшихся синих диагональных клеток и т.д. В итоге у нас получится непересекающихся путей, у каждого из которых разноцветные концы. Очевидно, на каждом из таких путей окажется хотя бы по одной разноцветной паре соседних по стороне клеток, так что мы сможем вырезать искомых доминошек.

Первое решение. Пусть — количество всех лабиринтов. Давайте рассмотрим плохие лабиринты, в которых огорожена какая-нибудь угловая клетка. Заметим, что таких плохих лабиринтов ровно В силу того, что нам нужно поставить две перегородки. Следовательно, хороших, в которых не огорожена эта угловая клетка точно меньше, чем Аналогично количество хороших лабиринтов, у которых не огорожено две угловых клетки точно меньше, чем а у которых не огорожено три угловых клетки точно меньше, чем Следовательно, хороших точно меньше половины, а значит, плохих больше.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Давайте думать о клетках, как о вершинах графа. Ребра будут общими сторонами, а если есть перегородка, то ребро убираем. Хорошим лабиринтам соответствует связный граф. Заметим, что в связном графе на вершинах должно быть хотя бы ребра. А значит, хороший лабиринт содержит не более перегородок. Давайте рассмотрим какой-нибудь лабиринт и определим для него инвертированный лабиринт, то есть в нашем графе мы убираем ребра и добавляем ребра, которых не было. Тогда мы получаем соответствие лабиринтов с перегородками лабиринтам с перегородками. То есть каждому хорошему лабиринту мы точно сопоставили плохой. А у нас точно еще есть плохие лабиринты, поэтому плохих лабиринтов точно больше.