|
|
 |
Условие
На плоскости отмечены все точки с целыми координатами (x,y) такие,
что x2+y2 1010 . Двое играют в игру (ходят по очереди).
Первым ходом первый игрок ставит фишку в какую-то отмеченную точку и
стирает ее. Затем каждым очередным ходом игрок переносит фишку в
какую-то другую отмеченную точку и стирает ее. При этом длины ходов
должны все время увеличиваться; кроме того, запрещено делать ход из
точки в симметричную ей относительно центра. Проигрывает тот, кто не может
сделать ход. Кто из играющих может обеспечить себе победу, как бы ни
играл его соперник?
Решение
Докажем более общее утверждение: Пусть игра с теми же правилами происходит на конечном множестве точек S , которое содержит точку O(0,0) и переходит
в себя при повороте на 90o . Тогда в этой игре выигрывает первый игрок. (Ясно, что множество точек из условия удовлетворяет этим условиям.)
Доказательство будем вести индукцией по количеству n точек в S . Если n=1 , то первый выигрывает первым своим ходом. Пусть n>1 .
Далее под отрезками мы всегда будем подразумевать отрезки, концы которых лежат в S и не симметричны относительно O .
Рассмотрим длины всех отрезков. Пусть d — максимальная из них, и пусть A1B1 , A2B2 , .. , AnBn — все отрезки длины d
(некоторые из точек Ai , Bj могут совпадать).
Заметим, что точка O не является концом ни одного из этих отрезков. Действительно, пусть это не так, и среди наших отрезков есть какой-то отрезок OA .
Пусть точка B S получается из A поворотом на 90o относительно O . Тогда AB=
OA>OA , то есть длина отрезка OA не
максимальна — противоречие.
Выкинем из S все точки Ai , Bi . Заметим, что полученное множество S' удовлетворяет всем условиям нашего утверждения (так как
множество отрезков AiBi переходит в себя при повороте на 90o ). Значит, по предположению индукции в игре на полученном множестве S'
выигрывает первый. Предъявим теперь выигрышную для него на множестве S .
Первый будет действовать по стратегии для множества S' с начала до того момента, когда второй впервые выведет фишку за пределы множества S' .
Это случится, ибо согласно стратегии для S' у первого всегда есть ход, после которого фишка остается в множестве S' .
Значит, рано или поздно второй сделает ход из точки X , лежащей в S' , в точку Y , не лежащую там (пусть тогда Y=Ai ).
Тогда первый может сделать ход в точку Bi (так как AiBi=d , а XAi<d , иначе бы X не лежала в S' ), после чего второму ходить некуда —
он должен сделать ход длины, большей d , а таких ходов нет. Итого, первый выигрывает.
Замечание. Аналогично доказывается, что, если множество S переходит в себя при повороте на 90o вокруг O , но не содержит ее,
то выигрывает второй.
