Задание №175398: Задание 3

3. В каждой клетке шахматной доски стоит нуль. Петя и Вася играют в игру. Ходят по очереди, начинает
Петя. Петя каждым своим ходом выбирает какой-то квадрат из четырех клеток и к каждому из чисел,
стоящих в этом квадрате, прибавляет нуль или единицу, по своему выбору (выбор для каждой из четырех
клеток совершается отдельно, то есть может случиться, что в некоторых клетках прибавляется нуль, а в
некоторых — единица). Вася своим ходом выбирает какую-то клетку и прибавляет к стоящему в ней числу
нуль или единицу, по своему выбору. Петя хочет, чтобы после 2024-го хода (т. е., после того как он и Вася
сделают по 1012 ходов) на доске было как можно больше нечетных чисел. Какое наибольшее количество
нечетных чисел он может получить независимо от действий Васи? (С. Берлов)
Ответ. 48. Решение. Пете надо разбить доску на 16 квадратов 22 и первыми 16-ю своими ходами прибавить ко
всем числам в каждом из них по единице. Вася за первые 16 своих ходов сможет заменить четными числами не
более 16 из этих единиц, так что после 32 ходов на доске будет не менее 48 нечетных чисел. Далее Пете
достаточно каждый раз прибавлять единицу к одному из стоящих на доске четных чисел, а к остальным числам
из содержащего эту клетку квадрата 22 — по нулю (или прибавлять ко всем числам выбранного квадрата по
0, если на доске все числа нечетные). Тогда после каждого хода Пети, начиная с 33-го, на доске будет не
меньше 49 нечетных чисел, а после каждого хода Васи, начиная с 33-го — не меньше 48. Васе же, для того,
чтобы после каждого его хода на доске было минимум 16 четных чисел, надо отметить 16 клеток на
пересечениях нечетных (считая слева) вертикалей доски с нечетными (считая снизу) ее горизонталями, и
каждым своим ходом восстанавливать четность числа в той клетке, в которой она была нарушена (а если нигде
не была — прибавить 0 к любой клетке). Это возможно, так как в каждый квадрат 22 попадает ровно одна
отмеченная клетка.