Library / /10 of 10

, 2018

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Saudi Arabia

Let $n > 2$ be a positive integer. Consider $n$ bags of candy, each of them has exactly 1 candy. Ali and Omar take turns playing the following game (Ali moves first): At each turn, the player takes two bags containing the numbers of candy as $x, y$ for some coprime integers $x, y$ and then merges them into one bag. Whoever cannot perform this action will be the loser. Who has the strategy to win this game?

Solution

We shall prove that for all $n > 2$ , Omar always has the strategy to win.

First, Ali has to merge some two bags of 1 candy into one bag of 2 candies. We prove that Omar can turn the state of all bags into: one bag contains odd number of candies and the others just have one candy each.

Indeed, in the second turn, Omar merges the bag of 2 candies with some bag of 1 candy to get one bag of 3 candies. Suppose that after a turn of Omar, there is a bag of $2k+1$ candies (with $k \in \mathbb{Z}^{+}$ ) and the other bags just have one candy each. At the next turn of Ali, there are two cases:

- If Ali merges two bags of 1 candy to one bag of 2 candies, then on the next turn, Omar merges that bag with the bag of $2k+1$ candies to get a bag of $2k+3$ candies.

- If Ali merges the bag of $2k+1$ candies with some bag of 1 candy to get another bag of $2k+2$ , then on the next turn, Omar merges that bag with some bag of 1 candy to get a bag of $2k+3$ candies.

Hence, Omar always can control the state of bags like that. Note that after two turns of players, the number of bags reduces by 2. Finally, if after a turn of Omar, there is only one bag of $2k+1$ candies then Ali will be the loser. Otherwise, there is a bag of $2k+1$ candies and 3 bags of 1 candy. There are two cases:

- If Ali merges two bags of 1 candy then Omar merges the bag of $2k+1$ with the bag of 1 candy; then after that turn, there are a bag of 2 candies and a bag of $2k+2$ which implies that Ali loses.

- If Ali merges the bag of $2k+1$ candies with a bag of 1 candy then Omar merges two bags of 1 candy to make two bags of even number of candies as above.

Therefore, in all cases of $n > 2$ , Omar always can win the game.

Want a route through all this instead of 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.