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$ гарантирует выигрыш