Задача 3. Нечётные на шахматной доске

Следим только за чётностью

Нас интересует только, какие числа нечётные, поэтому важна не сама величина числа, а его чётность. Прибавить $1$ — значит сменить чётность (чётное станет нечётным, нечётное — чётным), прибавить $0$ — ничего не менять.

На этом языке ход Пети такой: выбрать квадрат $2\times2$ и сменить чётность у любых клеток этого квадрата — у одной, двух, трёх, у всех четырёх или ни у одной. Ход Васи: сменить чётность одной клетки или ничего не менять.

Ходы с нечётными номерами $1, 3, \ldots, 2023$ делает Петя, с чётными $2, 4, \ldots, 2024$ — Вася. Значит, последний, $2024$-й ход — Васин, и считать нечётные числа нужно после ответа Васи.

Решение состоит из двух половин с одним и тем же числом:

• оценка: Вася может играть так, что нечётных в конце не больше этого числа, как бы ни ходил Петя;

• пример: Петя может играть так, что нечётных в конце не меньше этого числа, как бы ни ходил Вася.

Обе половины — стратегии, то есть правила, которые говорят, как ответить на любой ход соперника.

Стратегия Васи: охрана 16 клеток

Вася за ход меняет одну клетку, а Петя — до четырёх. Гоняться за всеми нечётными числами Васе бесполезно. Зато он может сторожить несколько клеток: как только одно из сторожевых чисел станет нечётным, следующим ходом прибавить к нему $1$ и вернуть в чётные.

Такая охрана работает, только если Петя одним ходом не может испортить сразу две сторожевые клетки — иначе Вася успеет вернуть лишь одну. Значит, никакие две сторожевые клетки не должны лежать в одном квадрате $2\times2$.

Пронумеруем строки и столбцы от $1$ до $8$ и возьмём клетки, у которых и номер строки, и номер столбца нечётны: строки $1, 3, 5, 7$ и столбцы $1, 3, 5, 7$. Таких клеток $4\cdot4=16$. В любом квадрате $2\times2$ ровно одна из них. Действительно, квадрат занимает две соседние строки, а из двух соседних номеров ровно один нечётный; так же из двух его соседних столбцов ровно один имеет нечётный номер. На пересечении этой строки и этого столбца и стоит единственная сторожевая клетка квадрата.

Стратегия Васи: если среди $16$ сторожевых чисел есть нечётное, прибавить к нему $1$; если все они чётные, прибавить $0$ к любой клетке.

Почему после каждого хода Васи все $16$ сторожевых чисел чётны? Вначале там нули. Пусть после очередного хода Васи они все чётны. Петя меняет клетки одного квадрата $2\times2$, а в нём только одна сторожевая клетка, — значит, нечётным может стать не больше одного сторожевого числа. Вася следующим ходом исправляет именно его, и снова все $16$ чётны. Так продолжается до конца игры.

После $2024$-го хода (а он Васин) на доске не меньше $16$ чётных чисел, значит, нечётных не больше $64-16=48$ — как бы ни играл Петя.

Стратегия Пети: сначала 16 блоков

Теперь покажем, что Петя может получить $48$ нечётных чисел при любой игре Васи.

Разрежем доску на $16$ квадратов $2\times2$ — назовём их блоками и пронумеруем от $1$ до $16$ (рисунок). Своим $k$-м ходом при $k=1, 2, \ldots, 16$ Петя берёт $k$-й блок и прибавляет $1$ к каждому чётному числу в нём, а к нечётным — $0$. Сразу после такого хода все четыре числа блока нечётны.

Заметим: Петя никогда не прибавляет $1$ к нечётному числу, то есть сам нечётное в чётное не превращает. Это может сделать только Вася, и одним ходом — не больше чем с одним числом.

Сосчитаем чётные числа сразу после $16$-го хода Пети. Каждое число в какой-то момент стало нечётным — когда Петя обработал его блок. Если сейчас оно чётное, то после этого его испортил Вася, причём разные такие числа испорчены разными ходами Васи. А Вася к этому моменту сделал только $15$ ходов. Поэтому чётных чисел не больше $15$, а после $16$-го хода Васи — не больше $16$.

Дальше Петя исправляет по одному

Начиная с $17$-го хода Петя действует так: если на доске есть чётное число, он берёт любой квадрат $2\times2$ с этой клеткой и прибавляет $1$ к этому числу (можно и ко всем чётным числам этого квадрата), а к нечётным — $0$. Если чётных чисел нет, он прибавляет $0$ ко всем числам любого квадрата.

Пусть перед ходом Пети чётных чисел не больше $16$. После его хода их не больше $15$: одно он исправил, а новых не создал (если чётных не было, их так и осталось $0$). Вася добавляет не больше одного чётного — снова не больше $16$. Значит, после каждого хода Васи, начиная с $16$-го, чётных не больше $16$ — в том числе после $2024$-го хода. Ходов Пете хватает с большим запасом: на обход блоков нужно всего $16$ ходов из $1012$.

Итак, после $2024$-го хода нечётных чисел не меньше $64-16=48$, как бы ни играл Вася.

Сводим две половины

По шагу 2 Вася может не дать Пете больше $48$ нечётных чисел. По шагам 3–4 Петя может получить не меньше $48$ при любой игре Васи. Поэтому наибольшее количество нечётных чисел, которое Петя может получить независимо от действий Васи, равно $48$.

Заметим, что обе стратегии держатся на одном и том же разрезании на квадраты $2\times2$: у Васи в каждом из них одна сторожевая клетка, у Пети каждый из них за один ход становится целиком нечётным. Поэтому и получается $64-16$.