In the plane, all the points with integer coordinates such that , are marked. Two players and play the following game. They move turn by turn. On the first move, places a token in some marked point and erases this point. After that, by each move the next player moves the token into some other marked point and erases this point. The constraints are the following. The length of each move should be strictly greater than the length of the previous move (made by the other player); moreover, it is prohibited to move the token from a point to the point symmetrical to it with respect to the origin. The player loses when he cannot make a move. Determine which player can win regardless by the opponent's moves.
Solution
Первый игрок выигрывает.
Докажем более общее утверждение: *Пусть игра с теми же правилами происходит на конечном множестве точек , которое содержит точку и переходит в себя при повороте на . Тогда в этой игре выигрывает первый игрок. (Ясно, что множество точек из условия удовлетворяет этим условиям.)*
Доказательство будем вести индукцией по количеству точек в . Если , то первый выигрывает первым своим ходом. Пусть . Далее под отрезками мы всегда будем подразумевать отрезки, концы которых лежат в и не симметричны относительно . Рассмотрим длины всех отрезков. Пусть — максимальная из них, и пусть — все отрезки длины (некоторые из точек могут совпадать).
Заметим, что точка не является концом ни одного из этих отрезков. Действительно, пусть это не так, и среди наших отрезков есть какой-то отрезок . Пусть точка получается из поворотом на относительно . Тогда , то есть длина отрезка не максимальна — противоречие.
Выкинем из все точки . Заметим, что полученное множество удовлетворяет всем условиям нашего утверждения (так как множество отрезков переходит в себя при повороте на ). Значит, по предположению индукции в игре на полученном множестве выигрывает первый. Предъявим теперь выигрышную для него на множестве .
Первый будет действовать по стратегии для множества с начала до того момента, когда второй впервые выведет фишку за пределы множества . Это случится, ибо согласно стратегии для у первого всегда есть ход, после которого фишка остается в множестве . Значит, рано или поздно второй сделает ход из точки , лежащей в , в точку , не лежащую там (пусть тогда ). Тогда первый может сделать ход в точку (так как , а , иначе бы не лежала в ), после чего второму ходить некуда — он должен сделать ход длины, большей , а таких ходов нет. Итого, первый выигрывает.