Раскраски

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

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