Competition problem — Combinatorics

Library / /45 of 55

Combinatorics Difficulty 6.8 National olympiad Prove it Ukraine

Suppose there are $2019$ points $A_1, A_2, \dots, A_{2019}$ in a circle, that form the regular $2019$ -gon $A_1A_2\dots A_{2019}$ . Olesya and Andrew take turns, Olesya is the first to go. According to certain rules, Olesya makes a move to form an obtuse triangle, and Andrew – an acute triangle. The rules for forming triangles are as follows. At the beginning vertices $A_1$ and $A_2$ are supposed to be marked. In the first step Olesya marks an unmarked vertex $A_i$ so that $\Delta A_1A_2A_i$ is formed and vertex $A_i$ becomes marked. Let in the next step Olesya (Andrew) marked an unmarked earlier vertex $A_j$ and formed an obtuse (acute) $\Delta A_kA_lA_j$ . Then in the next step Andrew (Olesya) can mark such an unmarked vertex $A_m$ , for which for an acute (obtuse) triangle $\Delta A_nA_jA_m$ is formed, where $n=k$ or $n=l$ . One loses if not able to follow the rules to make another move, that is to mark the vertex to form a proper triangle. Who wins the game if both players play correctly?

Solution

Let's place the circle so that the diameter through the vertex $A_1$ is vertical and this vertex itself is located below. Let's renumber all the vertices as shown on Fig. 44:

$A_i = B_{i-1},\ i = 1, 1010$ and
$A_i = B_{1010-i},\ i = 1011, 2019$ .

The strategy of Olesya is as follows: she always marks a vertex, that is symmetrical to the one Andrew marked with respect to the vertical diameter. In her first move she marks $B_{-1}$ . As we see, if vertex $B_i$ is not marked, then the vertex $B_{-i}$ is unmarked too and vice versa.

If Andrew is able to make a move, he marks some point $B_{-k}$ and $\Delta B_m B_l B_{-k}$ (Fig. 44). Since this triangle is acute, then the center of the circle is inside this triangle. Therefore, we will have a diameter $B_{-k}O$ , then vertices $B_m$ and $B_l$ lie on different sides of that diameter. One of them is located in one half-plane with a vertex $B_k$ , let's say, $B_m$ . Thus Olesya can mark vertex $B_k$ and $\Delta B_m B_{-k} B_k$ , it is obtuse, because it doesn't have the circle center inside.

Thus, Olesya will always be able to answer Andrew's move, even if all the vertices are marked, then Andrew will not be the first to make a move and lose.

Fig. 44

Looking for a route rather than 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.