|
|
 |
Условие
В таблице размера n×n клеток: две противоположные угловые клетки – чёрные, а остальные – белые. Какое наименьшее количество белых клеток достаточно перекрасить в чёрный цвет, чтобы после этого с помощью преобразований, состоящих в перекрашивании всех клеток какого-либо столбца или какой-либо строки в противоположный цвет, можно было сделать чёрными все клетки таблицы?
Решение
Пусть из некоторой раскраски 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 клетки.
