6-я олимпиада им. Шалтая Смагулова, 6 класс, 3 тур

Клетки черно-белой доски $12 \times 12$ раскрашены в шахматном порядке. Разрешается взять любые две соседние по стороне клетки и перекрасить их: черные клетки — в зеленый цвет, зеленые — в белый, белые — в черный. Какое наименьшее число таких операций потребуется, чтобы получить <<противоположную>> бело-черную шахматную раскраску?

Комментарий/решение

Оценка: Назовем фигуру "уголком", при удалении с квадрата 2х2 одной клетки. Есть два варианта уголка: 2 Б, 1 Ч; 2 Ч, 1 Б; Для уголка 2 Б, 1 Ч требуется не менее 2 операций, чтобы перекрасить в уголок 2 Ч, 1 Б; А чтобы перекрасить уголок 2 Ч, 1 Б в 2 Б, 1 Ч требуется не менее 4 операций. => $144/6*2+144/6*4=144$. Ответ: 144 операции.

Пример: Возмем прямоугольник $2*3$ и им заполним доску $12*12$.

(Б - белые клетки, Ч-черные).

эм чел не правильно

Не вижу ошибки. Если есть, то можете показать мой недочёт.

Ошибка в том, что вы делаете оценку по уголкам, то есть рассматриваете не все множество возможные способы перекраски, а только некоторое собственное подмножество этого множества. Соответственно возникает вопрос: а если сделать иначе, может быть есть и более короткий путь к цели.

Назовем ЧЕРНОЙ клетку, которая изначально была черной, а БЕЛОЙ, клетку, которая изначально была белой. Возьмем произвольную клетку. Если она БЕЛАЯ, то за один раз ее можно перекрасить в черный цвет. Таким образом, для перекраски всех БЕЛЫХ клеток в черные нужно как минимум 72 перекрашивания. Если же клетка ЧЕРНАЯ, то ее нужно перекрашивать минимум дважды, а значит все ЧЕРНЫЕ клетки можно перекрасить не меньше, чем за 144 перекрашивания. Заметим, что любая операция перекрашивает ровно одну БЕЛУЮ и ровно одну ЧЕРНУЮ клетку (тут неважно, в какой цвет закрашена данная БЕЛАЯ или ЧЕРНАЯ клетка в настоящий момент). Соответственно, чтобы перекрасить всю доску в "противоположную" шахматную раскраску, необходимо хотя бы 144 хода. Пример на 144 перекрашивания позволю себе процитировать из решения Abulmansur'а "Пример: Возмем прямоугольник $2\times 3$ и им заполним доску $12\times 12$". Разве что сделаю некоторые пояснения, очевидным образом доску можно разрезать на 24 прямоугольника, то есть на 48 уголков, из которых половина будет с центром в БЕЛОЙ клетке, а половина --- с центром в ЧЕРНОЙ клетке. Если посередине БЕЛАЯ клетка, то перекрасим по два раза каждую из угловых клеток уголка с центральной, если посередине ЧЕРНАЯ клетка, то достаточно по разу перекрасить каждую из угловых клеток уголка с центральной клеткой. Итого $24\cdot 4+ 24 \cdot 2=144$, что, собственно, и требовалось.