Решение. Полоса клеток (#89)

Ответ: 10

Решение

Назовём блоком последовательность клеток одного цвета. Например, в полосе на рисунке ниже 3 белых и 3 чёрных блока

Максимальное число чёрных блоков в полосе из двадцати клеток равно 10 (в полоске-зебре). В белой полосе число чёрных блоков равно нулю.

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

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

Следовательно, наименьшее число операций равно 10.

Решение (если нельзя перекрашивать одну клетку)

Определение. Инвариант — параметр, который не меняется при преобразовании

Определение. Полуинвариант — параметр, который меняется монотонно при преобразовании и лишь на конечное число возможных значений

Найдём полуинвариант операции. Пройдёмся по полосе слева направо и подсчитаем число n перемен цвета. В одноцветной полосе (белой или чёрной) число перемен цвета равно нулю (n=0). Заметим, что при перекрашивании прямоугольника число перемен цвета во всей полосе может уменьшиться не более, чем на 2. Это верно, потому что перемена цвета может исчезнуть только на границах прямоугольника, к которому применяется операция. C другой стороны, всегда можно уменьшить число перемен цвета на 1, перекрасив прямоугольник, одна из границ которого совпадает с концом полосы, а другая граница разделяет клетки разных цветов. Итак,

Полуинвариант = число перемен цвета в полосе (n)

Замечание. Строго говоря, число перемен цвета не будет полуинвариантом, если применять операцию к любому прямоугольнику. Всё потому, что число перемен цвета увеличивается после операции, если граница прямоугольника разделяет клетки одного цвета. К таким прямоугольникам мы применять операцию не будем, ведь наша цель свести число перемен цвета к 0.

Простая оценка. Из рассуждений выше следует, что можно сделать полосу одноцветной не более, чем за n операций (так как за одну операцию можно уменьшить полуинвариант на 1). Однако априори неизвестно, какого цвета она получится. Поэтому возможно потребуется ещё одна операция для перекрашивания в нужный цвет. Итак, для решения задачи заведомо потребуется не более n+1 операции.

Улучшим оценку. Для этого нужно (когда это возможно)

1. Уменьшать полуинвариант на 2

2. Добиваться сразу нужного цвета полосы при обнулении полуинварианта

Рассмотрим случаи. Будем выбирать прямоугольники для перекрашиваний определённым образом. Пронумеруем перемены цвета в полосе слева направо.

Пусть n≥3 нечётное

Первый прямоугольник будет от первой до последней перемены цвета.

Второй — от второй до предпоследней.

И так далее. После каждой операции полуинвариант уменьшается ровно на 2.

В конце концов останется одна перемена цвета в полосе. Причём, так как изначально n≥3, то справа и слева от границы перемены цвета будут прямоугольники (если бы мы перекрашивали прямоугольники произвольным образом, могло бы получится так, что с одной стороны от границы перемены цвета осталась бы одна клетка). Последняя операция — перекрашиваем чёрный прямоугольник в белый цвет — получаем полностью белую полосу.

Всего выполнили (n-1)/2 +1 = (n+1)/2 операций.

Пусть n≥4 чётное

Пока n>4, будем перекрашивать так же, как и в предыдущем случае.

Первый прямоугольник будет от первой до последней перемены цвета.

Второй — от второй до предпоследней.

И так далее. После каждой операции полуинвариант уменьшается ровно на 2. Как только полуинвариант стал равен 4, то оставшиеся прямоугольники перекрасим, как на рисунке 3.

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

Всего выполнили n/2 операций, если крайние клетки белые, или n/2 + 1 — если чёрные.

Остались также крайние случаи, которые мы не будем подробно разбирать ввиду их простоты.

Пусть n=1

В общем случае нужна 1 операция для получения одноцветной полосы, 2 операции — для белой полосы.

Пусть n=2

В общем случае нужно 2 операции для получения одноцветной полосы, 3 операции — для белой полосы.

Итого

Для полосы из 20 клеток достаточно посчитать два случая:

19 перемен цвета → (19+1)/2 = 10 операций

18 перемен цвета → 18/2 + 1 = 10 операций

Замечание.В приведённом решении неважен размер полосы (она может быть любой, но не менее трёх клеток, иначе нет решения), важно количество перемен цвета.

Подробнее про инварианты и полуинварианты можно прочитать в статье Л. Курляндчика и Д. Фомина «Этюды о полуинварианте» (Квант, 1989, выпуск 7)

Условие

Telegram