Задача 5. Два раза кистью

Какая доска осталась

Пронумеруем строки сверху вниз, а столбцы слева направо числами от $1$ до $100$; клетку в строке $a$ и столбце $b$ обозначим $(a,\,b)$. Вырезаны клетки, у которых номер строки чётный, а номер столбца нечётный. Значит, строки с нечётными номерами остались целыми, а в строках с чётными номерами уцелели только клетки чётных столбцов. Невырезанных клеток $100\cdot 100-50\cdot 50=7500$.

Каждый ход красит две клетки, а каждую клетку можно красить не больше двух раз. Если найдутся клетки, без которых не обходится ни один ход, то и ходов не может быть слишком много: каждый ход «тратит» одну из немногих покрасок этих клеток. Поищем такие клетки.

Назовём перекрёстком клетку на пересечении нечётной строки и чётного столбца, например $(1,\,2)$ или $(3,\,8)$. Такая клетка стоит в целой строке, и над ней и под ней тоже есть клетки — в ней сходятся горизонтальный и вертикальный пути. Перекрёстков $50\cdot 50=2500$: нечётных строк $50$, и в каждой $50$ чётных столбцов.

В каждом ходе есть перекрёсток

Возьмём любые две невырезанные клетки с общей стороной.

• Пусть они соседи по горизонтали, в строке $a$. Номера их столбцов — два соседних числа, одно чётное, другое нечётное. Если бы строка $a$ была чётной, клетка в нечётном столбце была бы вырезана. Значит, строка $a$ нечётная, и клетка в чётном столбце — перекрёсток.

• Пусть они соседи по вертикали, в столбце $b$. Номера их строк — соседние числа, одно чётное, другое нечётное. Если бы столбец $b$ был нечётным, клетка в чётной строке была бы вырезана. Значит, столбец $b$ чётный, и клетка в нечётной строке — перекрёсток.

Итак, каждый ход красит перекрёсток (ровно один: вторая клетка пары лежит в нечётном столбце или в чётной строке). Каждый перекрёсток можно покрасить не больше двух раз, поэтому ходов не больше чем

Зелёных клеток не больше, чем ходов

Возьмём клетку, которая в конце зелёная. Краски непрозрачные, поэтому её последняя покраска — зелёная, и эту зелёную краску клетка получила в каком-то ходе. У разных зелёных клеток это разные покраски, а за один ход Катя кладёт ровно одну зелёную краску. Значит,

Зелёных может оказаться и меньше, чем ходов: если зелёную клетку потом перекрасить в красный, её зелёная краска пропадёт зря. Поэтому для ровно $5000$ зелёных нужно сделать все $5000$ ходов — каждый перекрёсток покрасить дважды — и не перекрыть ни одной зелёной краски.

Пример: доска из уголков

Перекрёсток должен участвовать в двух ходах, то есть его нужно красить в паре с двумя разными соседями. Возьмём для перекрёстка $(a,\,b)$ соседа слева $(a,\,b-1)$ и соседа снизу $(a+1,\,b)$. Сосед слева есть, потому что $b\ge 2$, и он не вырезан: его строка $a$ нечётная. Сосед снизу есть, потому что $a\le 99$, и он не вырезан: его столбец $b$ чётный.

Перекрёсток с этими двумя соседями образует уголок из трёх клеток. Разные уголки не пересекаются: клетка нечётной строки и нечётного столбца входит только в уголок перекрёстка, стоящего справа от неё, а клетка чётной строки и чётного столбца — только в уголок перекрёстка над ней. Получается $2500$ уголков по $3$ клетки, то есть все $7500$ невырезанных клеток.

В каждом уголке Катя делает два хода:

• ход 1: сосед слева — зелёный, перекрёсток — красный;

• ход 2: перекрёсток — зелёный (поверх красного), сосед снизу — красный.

В каждом ходе две соседние невырезанные клетки, перекрёсток покрашен дважды, остальные клетки — по одному разу: правила выполнены, ходов $5000$, и ни одна зелёная краска не перекрыта. В конце зелёные все соседи слева и все перекрёстки — это в точности все клетки нечётных строк, $50\cdot 100=5000$ клеток. Красными остались $2500$ клеток чётных строк.

Оценка шагов 2–3 и этот пример вместе дают ответ: наибольшее число зелёных клеток — $5000$.

Второй вариант

Во втором варианте вырезаны клетки на пересечении нечётных строк и чётных столбцов, доска $200\times 200$, Андрей красит одну клетку синим, другую красным, а считаем красные. Невырезанных клеток $200\cdot 200-100\cdot 100=30\,000$.

Перекрёстками теперь назовём клетки на пересечении чётных строк и нечётных столбцов; их $100\cdot 100=10\,000$. Соседи по горизонтали в нечётной строке невозможны (клетка в чётном столбце вырезана), в чётной строке клетка нечётного столбца — перекрёсток. Соседи по вертикали в чётном столбце невозможны (клетка в нечётной строке вырезана), в нечётном столбце клетка чётной строки — перекрёсток. Значит, каждый ход красит перекрёсток, и ходов не больше $2\cdot 10\,000=20\,000$. Красная клетка — это красная последняя покраска, за ход кладётся одна красная краска, поэтому красных клеток не больше $20\,000$.

Пример: к перекрёстку $(a,\,b)$ присоединим соседа сверху $(a-1,\,b)$ (он есть, так как $a\ge 2$, и не вырезан: столбец $b$ нечётный) и соседа справа $(a,\,b+1)$ (он есть, так как $b\le 199$, и не вырезан: строка $a$ чётная). $10\,000$ таких уголков покрывают все $30\,000$ клеток. В каждом уголке два хода: 1) сосед сверху — красный, перекрёсток — синий; 2) перекрёсток — красный поверх синего, сосед справа — синий. Красными станут все соседи сверху и все перекрёстки — все клетки нечётных столбцов, $200\cdot 100=20\,000$ клеток. Ответ: $20\,000$.