27-я Балканская математическая олимпиада среди юниоров. Албания, 2023 год

Алиса и Боб играют в следующую игру на клетчатой доске $100\times 100$. Ходят по очереди, игру начинает Алиса. Изначально доска пуста. На каждом ходу игроку разрешается выбрать любое целое число от $1$ до $100^2$, которое еще не записано ни в одной из клеток, и записать это число в любую пустую клетку. После того, когда не останется пустых клеток на доске, Алиса вычисляет сумму чисел в каждой строке, и наибольшая из этих 100 сумм — это ее счёт. Боб вычисляет сумму чисел в каждом столбце, и наибольшая из этих 100 сумм — это его счёт. Алиса выигрывает, если ее счет больше, чем счет Боба, Боб выигрывает, если его счет больше, чем счет Алисы, в противном случае никто не выигрывает. Определите, есть ли у одного из игроков выигрышная стратегия, и если да, то у кого.

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

Разобьем таблицу на горизонтальные прямоугольники $2\times 1$. Рассмотрим сначала стратегию $B$, при которой всякий раз, когда $A$ записывает $x$ в некоторую ячейку прямоугольника $2\times 1$ (из вышеупомянутых), $B$ записывает $100^2 + 1 - x$ в другую ячейку того же прямоугольника. (Обратите внимание, что $x\neq 100^2 + 1 - x$, поскольку $100^2+1$ нечетно, поэтому такой ход $B$ всегда возможен.) В этом случае сумма чисел в каждой строке равна $50. \cdot (100^2 + 1)$, а поскольку суммирование по строкам и суммирование по столбцам дает один и тот же результат, должен существовать столбец с суммой, равной $50 \cdot (100^2 + 1)$. Следовательно, $A$ не может выиграть.

Чтобы обеспечить победу, $B$ достаточно немного подправить свою стратегию так, чтобы сумма в каждой строке оставалась прежней, но хотя бы в одном столбце сумма была больше $50 \cdot (100^2 + 1)$. Один из возможных способов сделать это следующий: если мы рассмотрим первые два прямоугольника $2\times 1$ в последней строке, то всякий раз, когда $A$ играет в ячейке одного из этих прямоугольников, $B$ играет в ячейке в другой прямоугольник. (Для всех остальных прямоугольников $2\times 1$ стратегия из первого абзаца не меняется.) Если от противного предположить, что $B$ не выигрывает, то единственная возможность состоит в том, что все комбинации имеют сумму $50 \cdot ( 100^2 + 1)$. Но поскольку $2\times 1$ прямоугольников в первых двух столбцах, кроме последнего, находятся пары чисел вида $(x, 100^2 + 1 - x)$ (с суммой $100^2 + 1$ ), то сумма чисел в прямоугольнике $2\times 1$ в последней строке (и в первых двух столбцах) равна $2\cdot 50 \cdot (100^2 + 1) - 99 \cdot (100 ^2 + 1) = 100^2 + 1$, поэтому он также состоит из пары вида $(t, 100^2 + 1 - t)$, что противоречит стратегии $B$. Следовательно, $B$ гарантирует выигрыш