55rd Ukrainian National Mathematical Olympiad - Fourth Round

Answer: a) Andriy wins, b) Olesya wins.

Clearly, the one who is forced to draw a chord from the point from which there is another chord drawn already, will lose (Fig. 39). For example, one player draws $AC$ and chord $AB$ has already been drawn before (we assume that there are no other chords drawn from point $A$ except these two). Then the other player just draws a chord $BC$ and wins. It is obvious that this chord can be drawn, because if else, it would have crossed some other chord - $MN$, for example, and then one of the points, let's say $M$, would belong to the arc $\cup BC$, and another one wouldn't. Which means the point $N$ would belong to the arc $\cup AB$, and then $MN$ would cross $AB$, or it would belong to $\cup AC$ and then $MN$ would cross $AC$.

So the game will continue until one of the players will be forced to draw a second chord from one point and, as the result, to lose. It means that in the beginning both players will draw only chords that connect the "free" points (those points that have no chords drawn from them yet). At any moment all the free points can be divided into "groups" within each of which we can connect any two points. Moreover, the chords within the group are independent of other groups and do not affect other groups. So the position after each move can be written as a list of groups, by the number of free points in it. If the next chord is drawn in a group containing $m$ points, then instead of the old group there are two groups created containing $m_1$ and $m_2$ points, where $m_1+m_2=m-2$ (note that one or both groups may be empty). Thus, the starting point for $N=15$ can be written as (15), and after the first chord may form, for example, a position (10; 3), (8; 5), or (13; 0), etc. After the next move there will be 3 groups, and note that groups with (0) or (1) can be ignored, because we can't draw a chord there that would not lead to defeat.

Now let us show some simple properties of groups of points that will shorten the process of analyzing the current situation.

Property 1. In the group with 3 points one can always draw one chord, in the group with 5 points one can always draw 2 chords.

Property 2. In the group with 4 points the one who draws a chord within this group may choose any of the two options for partitioning, (1; 1) or (2; 0), so there can be drawn either one or two chords, depending on this player's move.

Property 3. In the group with 6 points the one who draws a chord within this group may choose one of the these options for partitioning: (2; 2) or (3; 1), so that there can be drawn 3 or 2 chords.

Property 4. If there is a symmetrical situation (i.e. groups of points can be divided into pairs containing equal number of points), the winner is the one whose move resulted in such symmetrical situation.



Proving these properties is almost obvious and can be easily conducted by going through each of those variants. Let us explain the property 4. If after the move of one of the players we get the situation $(k;k)$, he wins by using moves symmetric to his/her opponent's moves. There are other symmetric situations, but they are just this situation's analogues.

Let's agree to not further specify the groups (1) and (0), because they do not affect the further course of the game.

a) Andriy wins due to move (6; 6), as his victory follows from property 4 through further symmetrical strategy.

b) Olesya wins. Let's look at the possible first moves of Andriy.

Option 1. (13): Olesya wins due to move (8; 3). Let's look at the possible answers of Andriy.

Version 1.1. (8): (Actually it was a move (8; 1; 0) but we do not specify the last two groups). Then Olesya goes (3; 3) and wins due to the symmetrical strategy.

Version 1.2. (3; 6): Since there is a group (3), where one move is possible, and the group (6) where Olesya can choose how many moves the game will last, then she breaks group (6) accordingly - making a move into position (3; 6) $\to$ (3; 3).

Version 1.3. (3; 5): The game lasts exactly three moves, Olesya's move is the last and she wins.

Version 1.4. (3; 4; 2): due to group (4) Olesya wins. She should leave the groups (2,3).

Version 1.5. (3; 3; 3): Obviously, Olesya wins.

Option 2. (12) $\to$ (5; 5) and Olesya wins.

Option 3. (11; 2) $\to$ (8; 2) Andriy has such options:

(6; 2), Olesya goes (3; 2) and wins.

(5; 2), exactly three moves left. Thus, Olesya wins.

(4; 2; 2), Olesya makes a move in a group with 4 points into (2; 2) and wins.

(3; 2; 2), exactly three moves left. Which means Olesya wins.

Option 4. (10; 3) $\to$ (5; 3; 3) and the game will continue for another four moves, meaning Olesya wins.

Option 5. (9; 4) $\to$ (9). Then there are several sub-variants possible, which easily lead to Olesya's victory: (9) $\to$ (7) $\to$ (5) or (9) $\to$ (6) $\to$ (2; 2) or (9) $\to$ (4; 3) $\to$ (2; 3).