Комбинаторика на Питергоре

Оценка.

Покажем, что ходов обязательно придётся сделать.

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

Второй способ. Предположим, что мы сделали менее ходов. Тогда найдётся строка, которую мы не задействовали. Но в этой строке в результате появилось чёрных клеток, значит, было сделано как минимум “вертикальных” ходов. Аналогично показывается, что было сделано как минимум “горизонтальных” ходов, т.е. всего не менее ходов.

Пример.

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