Задание №177218: Турнир городов

4. Клетки доски 100 × 100 раскрашены в чёрный и белый цвета в шахматном порядке.
Можно ли перекрасить ровно 2018 различных клеток этой доски в противоположный цвет
так, чтобы в каждой строке и в каждом столбце оказалось одно и то же количество
чёрных клеток?
Ю. Чеканов
Ответ. Нет.
Решение 1. Ясно, что строки доски можно переставлять как угодно, и столбцы тоже.
Переставим все нечётные столбцы влево, а все нечётные строки вниз. В итоге из исходной
доски получится доска, разделённая на 4 одинаковых квадрата — два противоположных из
них белые, а остальные чёрные.
Пусть после перекраски в каждой строке и каждом столбце оказалось по 50 + k чёрных
клеток; тогда в каждом столбце и в каждой строке перекрашено на k белых клеток больше,
чем чёрных. Пусть в одном из чёрных квадратов перекрашено a клеток. По замечанию выше, в
каждом из белых квадратов перекрашено по a+50k клеток, а тогда в другом чёрном квадрате
также перекрашено (a + 50k) − 50k = a клеток. Значит, общее число перекрашенных клеток
равно 2a + 2(a + 50k) = 4(a + 25k), то есть оно делится на 4 и потому не может равняться
2018.
Решение 2. Пронумеруем строки снизу вверх, а столбцы справа налево, числами от 1 до 100
(пусть левая нижняя клетка чёрная). Тогда у каждой чёрной клетки чётная сумма координат,
а у каждой белой — нечётная.

Рассмотрим сумму координат всех чёрных клеток (до или после перекраски). Поскольку
в каждой строке их поровну, сумма их ординат делится на 1+2+...+100 = 5050, аналогично
сумма абсцисс также делится на 5050. В частности, эта сумма до и после перекраски была
чётной, то есть изменилась на чётное число.
С другой стороны, при перекраске исходно чёрной клетки в белый цвет наша сумма чёт-
ности не меняла, а при перекраске исходно белой в чёрный — меняла. Это значит, что было
перекрашено чётное количество белых клеток.
Пусть w и b — количества перекрашенных исходно белых и исходно чёрных клеток, соот-
ветственно. Тогда w+b = 2018, а w−b делится на 4, поскольку как исходное, так и полученное

количество чёрных клеток делится на 4. Значит, w = ((w + b) + (w − b))/2 — нечётное число.
Противоречие.