Problem

Source: Third Saudi Arabia JBMO TST 2018, P4

Tags: combinatorics



Let $n> 2$ be a natural number. We consider $n$ candy bags, each containing exactly one candy. Ali and Omar play the following game in which they move alternately (Ali moves the first): At each move, the player who has to make a move chooses two bags containing $x$, respectively $y$ candy, with $(x,y)=1$, and he puts the $x + y$ candies in one bag (he chooses where). The player who can't make a move loses. Which of the two players has a strategy to win this game?