Maths Olympiad Prep

Library / /46 of 46

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it Russia

In the plane, all the points with integer coordinates (x,y)(x, y) such that x2+y21010x^2 + y^2 \le 10^{10}, are marked. Two players AA and BB play the following game. They move turn by turn. On the first move, AA 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.

(I.Bogdanov)(I. Bogdanov)

Solution

Первый игрок выигрывает.

Докажем более общее утверждение: *Пусть игра с теми же правилами происходит на конечном множестве точек SS, которое содержит точку O(0,0)O(0,0) и переходит в себя при повороте на 9090^\circ. Тогда в этой игре выигрывает первый игрок. (Ясно, что множество точек из условия удовлетворяет этим условиям.)*

Доказательство будем вести индукцией по количеству nn точек в SS. Если n=1n=1, то первый выигрывает первым своим ходом. Пусть n>1n > 1. Далее под отрезками мы всегда будем подразумевать отрезки, концы которых лежат в SS и не симметричны относительно OO. Рассмотрим длины всех отрезков. Пусть dd — максимальная из них, и пусть A1B1,A2B2,,AnBnA_1B_1, A_2B_2, \dots, A_nB_n — все отрезки длины dd (некоторые из точек Ai,BjA_i, B_j могут совпадать).

Заметим, что точка OO не является концом ни одного из этих отрезков. Действительно, пусть это не так, и среди наших отрезков есть какой-то отрезок OAOA. Пусть точка BSB \in S получается из AA поворотом на 9090^\circ относительно OO. Тогда AB=2OA>OAAB = \sqrt{2} OA > OA, то есть длина отрезка OAOA не максимальна — противоречие.

Выкинем из SS все точки Ai,BiA_i, B_i. Заметим, что полученное множество SS' удовлетворяет всем условиям нашего утверждения (так как множество отрезков AiBiA_iB_i переходит в себя при повороте на 9090^\circ). Значит, по предположению индукции в игре на полученном множестве SS' выигрывает первый. Предъявим теперь выигрышную для него на множестве SS.

Первый будет действовать по стратегии для множества SS' с начала до того момента, когда второй впервые выведет фишку за пределы множества SS'. Это случится, ибо согласно стратегии для SS' у первого всегда есть ход, после которого фишка остается в множестве SS'. Значит, рано или поздно второй сделает ход из точки XX, лежащей в SS', в точку YY, не лежащую там (пусть тогда Y=AiY = A_i). Тогда первый может сделать ход в точку BiB_i (так как AiBi=dA_iB_i = d, а XAi<dXA_i < d, иначе бы XX не лежала в SS'), после чего второму ходить некуда — он должен сделать ход длины, большей dd, а таких ходов нет. Итого, первый выигрывает.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.