4. The first $n$ positive integers are written on the board. Markéta and Tereza take turns in the following game. First, Markéta erases one of the numbers on the board. Then, on each turn, the player whose turn it is erases one of the numbers that differs from the previously erased number by neither 1 nor is coprime with it. The player who is on turn and cannot erase any more numbers loses. Decide which of the players can play in such a way that they win regardless of the moves of the other player for $n=6$ and for $n=12$.

The regional round of category C takes place

## on Tuesday, April 17, 2012

so that it starts in the morning and the participants have 4 hours of pure time to solve the problems. For each problem, a participant can earn 6 points, and a successful solver is a student who scores 10 points or more. Allowed aids are writing and drawing tools and school MF tables. Calculators, laptops, and any other electronic aids are not allowed. These details will be communicated to the students before the start of the competition.
4. The role of two consecutive permissible numbers in the given game is symmetric: if the number $y$ can be erased after the number $x$, then (in a different course of the game) the number $x$ can be erased after the number $y$. Therefore, we can "clarify" the entire game (with the given number $n$) by listing all such (let's call them permissible) pairs $(x, y)$. Since the order of the numbers in a permissible pair does not matter, it is sufficient to list only those pairs $(x, y)$ where $x < y$.

In the case of $n=6$, all permissible pairs are

$$
(1,3),(1,4),(1,5),(1,6),(2,5),(3,5) \text {. }
$$

From this list, we can easily conclude that the first player, Markéta, has a winning strategy. If she erases the number 4 at the beginning of the game, Tereza must erase the number 1, and when Markéta then erases the number 6, Tereza can no longer erase any other number. Besides this sequence $4 \rightarrow 1 \rightarrow 6$, Markéta can ensure victory through other "forced" sequences for Tereza, such as $6 \rightarrow 1 \rightarrow 4$ or $4 \rightarrow 1 \rightarrow 3 \rightarrow 5 \rightarrow 2$.

In the case of $n=12$, the number of permissible pairs is significantly larger. Therefore, we ask whether all numbers from 1 to 12 can be divided into six permissible pairs. If we find such a set of six pairs, we can describe a winning strategy for the second player (Tereza): if Markéta erases a number $x$ on any of her turns, Tereza will then always erase the number $y$ that forms one of the six found pairs with $x$. In this way, Tereza will eventually erase the last (twelfth) number and win.

The desired division of all 12 numbers into six pairs does indeed exist, for example,

$$
(1,4),(2,9),(3,8),(5,12),(6,11),(7,10)
$$

Another valid division can be obtained by swapping the pairs $(1,4)$ and $(6,11)$ in the previous set with the pairs $(1,6)$ and $(4,11)$. Another, less similar valid division is, for example,

$$
(1,6),(2,5),(3,10),(4,9),(7,12),(8,11)
$$

Answer: For $n=6$, Markéta has a winning strategy, and for $n=12$, Tereza has a winning strategy.

For a complete solution, award 6 points, with 2 points for solving the case $n=6$ and 4 points for solving the case $n=12$.


[^0]:    1 The equality is derived by expanding the lengths of the sides into segments defined by the points of tangency of the inscribed circle and then using the fact that any two of these segments that originate from the same vertex of the quadrilateral are equal.