The numbers $1,2,3,\ldots ,n$ are written in a row. Two players, Maris and Filips, take turns making moves with Maris starting. A move consists of crossing out a number from the row which has not yet been crossed out. The game ends when there are exactly two uncrossed numbers left in the row. If the two remaining uncrossed numbers are coprime, Maris wins, otherwise Filips is the winner. For each positive integer $n\ge 4$ determine which player can guarantee a win.
Problem
Source: Latvian TST for Baltic Way 2022 P6
Tags: combinatorics
26.11.2022 02:14
The problem is directly based on this post, however, here the bound is lowered (it is not difficult to deal with the small cases, yet, they do require dedicated attention).
21.03.2024 16:53
Answer: for n $\le$ 9 and odd n's wins $\boxed{Maris}$, for even n $\ge$ 10 wins $\boxed{Fillips}$. Let's look at 2 cases: 1) n is odd In the first move, Maris crosses out n, and creates a new game Fillips starting first and n being even. Now, let's divide numbers into $\frac{n-1}{2}$ groups: {1; 2}, {3; 4}, ..., {n-2; n-1}. Fillips starts first, so Maris can cross out groups from which Fillips selected a number. Then, uncrossed numbers would be consecutive and coprime. So, $\boxed{Maris}$wins. 2) n is even 2.1) n $\le$ 8 It's easy to see that for n=4, 6, 8, $\boxed{Maris}$ wins by crossing even numbers except 2. 2.2) n $\ge$ 10 There are $\frac{n}{2}$ even numbers, and Maris has $\frac{n-2}{2}$ moves. So if Fillips won't cross out even numbers, Maris can only cross out even numbers(2 even numbers aren't coprime) and cannot cross out odd numbers. Then, if Fillips will cross out only odd numbers except 3 and 9 in the first $\frac{n-4}{2}$ moves and then will cross out 1 even number left in the last move, $\boxed{Fillips}$ will win.