J. Задача B5. Перекрашивание доски (17 баллов). Первоначально все клетки доски 101 × 101 покрашены в белый цвет. Ход состоит в том, что выбирается квадрат 2 × 2 и все его белые клетки перекрашиваются в чёрный цвет, а все его чёрные клетки — в белый. Какое наименьшее число белых клеток может остаться на доске после серии таких ходов?

Представим цвета клеток числами по модулю 2: белая клетка — 1, чёрная — 0. Один ход меняет цвет четырёх клеток выбранного квадрата 2 × 2.

Рассмотрим чётность числа белых клеток в каждой строке. Ход либо не затрагивает строку, либо меняет цвет ровно двух её клеток, поэтому чётность числа белых клеток в строке сохраняется. Аналогично сохраняется чётность в каждом столбце.

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

Эта граница достижима: раскраска, в которой белые клетки стоят по одной в каждой строке и каждом столбце, а остальные клетки чёрные, достижима ходами 2 × 2. Действительно, разность между исходной и такой раскрасками имеет чётное число единиц в каждой строке и столбце; всякую такую матрицу можно получить суммой по модулю 2 матриц квадратов 2 × 2.

Ответ: 101.