Подсчеты в клетчатых задачах

Докажем утверждение от противного. Пусть есть раскраска, при которой отсутствует пара параллельных линий с одинаковым числом черных клеток. Будем называть весом линии количество черных клеток на ней. Пусть есть горизонталь веса Тогда вертикалей и диагоналей каждого направления должны иметь веса так как все они пересекают эту горизонталь. Тогда и горизонталей имеют веса так как все они пересекают вертикаль веса Циклически переставим горизонтали и вертикали так, чтобы нижняя горизонталь и левая вертикаль имели вес (свойства раскраски при этом не изменятся). Пронумеруем горизонтали снизу вверх от до а вертикали — от до слева направо. Каждая диагональ пересекает по разу горизонталь и вертикаль веса поэтому диагонали веса должны проходить через клетку их пересечения — клетку Итак, все клетки и не закрашены.

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