Задача 115399

Темы:    [ Поворот на $90^\circ$ ] [ Наименьшее или наибольшее расстояние (длина) ] [ Метод координат на плоскости ] [ Теория игр (прочее) ]

Сложность: 6- Классы: 9,10,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 , но не содержит ее, то выигрывает второй.

Источники и прецеденты использования

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	2008-2009
Этап
Вариант	5
Класс
Класс	11
задача
Номер	06.4.11.4