Олимпиадная задача по комбинаторной геометрии: минимальное перекрашивание клеток в таблице

  Пусть из некоторой раскраски P можно указанными преобразованиями сделать полностью чёрный квадрат. Тогда те же преобразования в обратном порядке переведут полностью чёрный квадрат в раскраску P . При каждом из этих преобразований одинаково раскрашенные строки или противоположно раскрашенные строки (то есть строки, соответствующие клетки которых раскрашены в разные цвета) переходят также в одинаково или противоположно раскрашенные. Следовательно, все строки раскраски P были одинаково или противоположно раскрашены. Наоборот, из каждой раскраски с этим свойством можно указанными преобразованиями сделать сначала все строки одинаковыми, а затем – и полностью чёрными. Каждая такая раскраска удовлетворяет одному из следующих условий.

  1) В каждой строке все клетки одного цвета. Тогда из условия следует, что в первой и последней строках все клетки чёрные, то есть всего чёрных клеток не менее 2n.

  2) В каждой строке есть не менее двух чёрных клеток, то есть всего чёрных клеток не менее 2n.

  3) Существует строка, в которой ровно одна чёрная клетка. Тогда либо первая, либо последняя строка с ней не совпадает и, следовательно, противоположна ей, то есть содержит  n – 1  чёрную клетку. В этом случае общее число чёрных клеток не меньше  (n – 1)·1 + 1·(n – 1) = 2n – 2.

  Таким образом, в любом случае в раскраске P должно быть не менее  2n – 2  чёрных клеток. Значит, число клеток, которые нужно предварительно перекрасить, должно быть не меньше  2n – 4.  На рисунке изображён квадрат n×n, все строки которого раскрашены одинаково или противоположно, а число предварительно перекрашенных в чёрный цвет клеток равно  2n – 4.

2n – 4  клетки.