|
|
 |
Условие
Петя и Вася независимо друг от друга разбивают белую клетчатую доску $100\times 100$ на произвольные группы клеток, каждая из чётного (но не обязательно все из одинакового) числа клеток, каждый – на свой набор групп. Верно ли, что после этого всегда можно покрасить по половине клеток в каждой группе из разбиения Пети в чёрный цвет так, чтобы в каждой группе из разбиения Васи было поровну чёрных и белых клеток?Решение 1
Заметим, что частным случаем разбиений является ситуация, когда каждая из Петиных и Васиных групп содержит в точности две клетки. С другой стороны, любое разбиение на группы из чётного числа клеток можно измельчить на группы из двух клеток, и если существует требуемая раскраска для измельченных разбиений, то та же самая раскраска, очевидно, решает задачу и для исходных разбиений.Теперь каждую Васину группу (из двух клеток), совпадающую с какой-то из Петиных групп, покрасим в чёрный и белый цвет любым из двух способов – одну клетку в чёрный, другую в белый цвет.
Осталось раскрасить множество клеток, которое Васей и Петей разбито на пары так, что ни одна Васина пара не совпадает с Петиной парой.
Построим граф, вершины которого соответствуют Васиным и Петиным группам (у Васи и Пети, очевидно, одно и то же количество групп). Две вершины соединим ребром тогда и только тогда, когда соответствующие группы имеют общую клетку. Тогда каждая вершина графа имеет степень два, причём любое ребро соединяет одну из вершин, соответствующих Васиным группам, с одной из вершин, соответствующих Петиным группам.
Такой граф разбивается на циклы, причём каждый цикл имеет чётную длину
(за счёт того, что в нём чередуются вершины, соответствующие Васиным и
Петиным группам) и допускает раскраску в два цвета, при которой цвета
рёбер чередуются вдоль цикла. Наконец, цвету клетки сопоставим цвет
ребра, соединяющего две вершины графа, соответствующие Васиной и
Петиной группам, пересекающимся по данной клетке. Полученная
раскраска удовлетворяет условию задачи.
Решение 2
Для удобства назовём непересекающиеся группы клеток одного разбиения (Пети или Васи) фигурками.Построим вспомогательный двудольный граф $G$. Для каждой из фигурок одного из разбиений (Пети или Васи) добавим в граф $G$ новую, соответствующую этой фигурке вершину. При этом вершины, соответствующие фигуркам Пети, отнесём к первой доле, а вершины, соответствующие фигуркам Васи, – ко второй. Далее проведём рёбра между некоторыми вершинами графа $G$ по следующему правилу: если фигурка Пети $A$ пересекается с фигуркой Васи $B$ по нечётному количеству клеток, то проведём между соответствующими этим фигуркам вершинами ребро.
Заметим, что в построенном графе степень каждой вершины чётна. Действительно, выберем, например, произвольную фигурку Васи $A$. Поскольку $A$ состоит из чётного числа клеток и пересекается лишь с фигурками из разбиения Пети, то по нечётному количеству клеток она будет пересекаться с чётным количеством фигурок.
Рассмотрим произвольную компоненту связности $G$. Поскольку степень каждой вершины этой компоненты чётна, то существует цикл (так называемый эйлеров цикл), проходящий по всем рёбрам этой компоненты ровно по $1$ разу. Выберем такие циклы для каждой компоненты связности $G$. Для удобства назовём полученное разбиение рёбер графа $G$ на циклы $\Omega$.
Теперь построим искомую раскраску фигурок в разбиении Пети. Выберем произвольный цикл $\sigma$ из построенного разбиения $\Omega$ и ориентируем его рёбра в каком-то из двух возможных естественных направлений его обхода. Рассмотрим произвольное (уже ориентированное) ребро $e$ цикла $\sigma$. Пусть оно соединяет вершины, соответствующие фигуркам $A$ и $B$. По построению фигурки $A$ и $B$ пересекаются по нечётному количеству клеток. Пусть они пересекаются по $2k+1$ клетке. Тогда если ребро $e$ ведёт из первой доли во вторую, то Петя покрасит в чёрный цвет произвольные $k$ из этих клеток, в противном случае – произвольные $k+1$ из них. Пусть Петя выполнит аналогичную покраску для каждой компоненты связности $G$. Наконец, пусть для каждой пары фигурок $A$ и $B$, пересекающихся по чётному количеству клеток, Петя покрасит ровно половину клеток в их пересечении в чёрный цвет.
Докажем, что полученная покраска будет искомой. Рассмотрим, например,
произвольную фигурку Пети $A$. Пусть $B$ – произвольная фигурка
Васи. Заметим, что среди общих клеток фигурок $A$ и $B$ разность числа
чёрных и белых клеток равна $\pm 1$ или $0$, в зависимости от чётности
числа клеток в этом пересечении. Поэтому достаточно доказать, что
разность $+1$ встречается среди пересечений фигурки Пети $A$ с
фигурками Васи столько же раз, сколько и разность $-1$. Пусть фигурке
$A$ в графе $G$ соответствует вершина $v$, которая лежит в некотором
цикле $\sigma$ из построенного ранее разбиения $\Omega$. Тогда каждой
разности $+1$ соответствует ребро цикла $\sigma$, входящее в $v$, а
каждой разности $-1$ – ребро цикла $\sigma$, исходящее из $v$. Из
построения цикла $\sigma$ следует, что рёбер, входящих в $v$, в нём
будет столько же, сколько и рёбер, исходящих из $v$. Поэтому фигурок
Васи, в клетках пересечения $A$ с которыми будет ровно на одну чёрную
клетку больше, будет столько же, сколько фигурок Васи, в клетках
пересечения $A$ с которыми будет ровно на одну белую клетку
больше. Таким образом, в фигурке $A$ поровну чёрных и белых клеток,
что и требовалось доказать.
