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

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

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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