Олимпиадная задача по планиметрии и теории алгоритмов: выигрышная стратегия с фишкой на целых точках (Богданов И. И.)

Задача 215399 • Сложность: 5 • 9-11 класс

Задача

На плоскости отмечены все точки с целыми координатами (x,y)такие, что x²+y² 1010. Двое играют в игру (ходят по очереди). Первым ходом первый игрок ставит фишку в какую-то отмеченную точку и стирает ее. Затем каждым очередным ходом игрок переносит фишку в какую-то другую отмеченную точку и стирает ее. При этом длины ходов должны все время увеличиваться; кроме того, запрещено делать ход из точки в симметричную ей относительно центра. Проигрывает тот, кто не может сделать ход. Кто из играющих может обеспечить себе победу, как бы ни играл его соперник?

Решение

Докажем более общее утверждение: Пусть игра с теми же правилами происходит на конечном множестве точек S , которое содержит точку O(0,0)и переходит в себя при повороте на90^o . Тогда в этой игре выигрывает первый игрок. (Ясно, что множество точек из условия удовлетворяет этим условиям.) Доказательство будем вести индукцией по количеству n точек в S . Если n=1, то первый выигрывает первым своим ходом. Пусть n>1. Далее под отрезками мы всегда будем подразумевать отрезки, концы которых лежат в S и не симметричны относительно O . Рассмотрим длины всех отрезков. Пусть d — максимальная из них, и пусть A₁B₁ , A₂B₂ , .. , A_nB_n — все отрезки длины d (некоторые из точек A_i , B_j могут совпадать). Заметим, что точка O не является концом ни одного из этих отрезков. Действительно, пусть это не так, и среди наших отрезков есть какой-то отрезок OA . Пусть точка B S получается из A поворотом на90^o относительно O . Тогда AB= OA>OA , то есть длина отрезка OA не максимальна — противоречие. Выкинем из S все точки A_i , B_i . Заметим, что полученное множество S' удовлетворяет всем условиям нашего утверждения (так как множество отрезков A_iB_i переходит в себя при повороте на 90^o ). Значит, по предположению индукции в игре на полученном множестве S' выигрывает первый. Предъявим теперь выигрышную для него на множестве S . Первый будет действовать по стратегии для множества S' с начала до того момента, когда второй впервые выведет фишку за пределы множества S' . Это случится, ибо согласно стратегии для S' у первого всегда есть ход, после которого фишка остается в множестве S' . Значит, рано или поздно второй сделает ход из точки X , лежащей в S' , в точку Y , не лежащую там (пусть тогда Y=A_i ). Тогда первый может сделать ход в точку B_i (так как A_iB_i=d , а XA_i<d , иначе бы X не лежала в S' ), после чего второму ходить некуда — он должен сделать ход длины, большей d , а таких ходов нет. Итого, первый выигрывает.Замечание.Аналогично доказывается, что, если множество S переходит в себя при повороте на90^o вокруг O , но не содержит ее, то выигрывает второй.