Maths Olympiad Prep

Library / /10 of 10

Combinatorics Difficulty 6.8 National olympiad Prove it Austria

Let n2n \ge 2 be an integer.
Ariane and Bérénice play a game on the set of residue classes modulo nn. In the beginning, the residue class 11 is written on a piece of paper. In each move, the player whose turn it is replaces the current residue class xx with either x+1x+1 or 2x2x. The two players alternate with Ariane starting.
Ariane has won if the residue class 00 is reached during the game. Bérénice has won if she can permanently avoid this outcome.
For each value of nn, determine which player has a winning strategy.

Solution

Answer. Ariane wins for n=2,4n = 2, 4 and 88, for all other n2n \ge 2 Bérénice wins.

We observe: If Ariane can win for a certain nn, she will also win for all divisors of nn, and conversely, if Bérénice can win for a certain nn, she will also win for all multiples of nn because a residue 00 modulo nn is automatically a residue 00 for all divisors of nn.
It remains to show that Ariane wins for n=8n = 8 and Bérénice wins for n=16n = 16 and nn odd.
All congruences in this solution are modulo nn.

* For n=8n = 8, Ariane has to choose 22 in the first step. If Bérénice takes 44, Ariane can choose 808 \equiv 0 and has won. If Bérénice takes 33, Ariane can choose 66. Now, Bérénice has to decide between 77 and 26=1242 \cdot 6 = 12 \equiv 4. But for both, Ariane can immediately choose 808 \equiv 0.

* For n=16n = 16, Bérénice chooses 2x2x for all numbers except 44 and 88. This clearly never gives the residue classes 00, 1515 or 88, so that Ariane also cannot choose 00.

* For n=3n = 3, Ariane has to choose 22 in the first step and then Bérénice chooses 11 again, which means that Bérénice wins.

* For odd n>3n > 3, it is not possible to reach 00 with 2x2x from another residue class. So the only possible issue for Bérénice would be the situation that both her options are among nn and n1n-1 such that she or Ariane choose 00. But this means that x+1x+1 takes the residues 00 or 1-1, so 2x2x takes the residues 2-2 or 4-4 which are both different from 00 and 1-1, so this cannot happen and Bérénice can permanently avoid 00 being chosen.

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.