Problem

Source: Latvian TST for Baltic Way 2022 P6

Tags: combinatorics



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.