C3 Alphonse and Beryl play the following game. Two positive integers $m$ and $n$ are written on the board. On each turn, a player selects one of the numbers on the board, erases it, and writes in its place any positive divisor of this number as long as it is different from any of the numbers previously written on the board. For example, if 10 and 17 are written on the board, a player can erase 10 and write 2 in its place (as long as 2 has not appeared on the board before). The player who cannot make a move loses. Alphonse goes first.
(a) Suppose $m=2^{40}$ and $n=3^{51}$. Determine which player is always able to win the game and explain the winning strategy.
(b) Suppose $m=2^{40}$ and $n=2^{51}$. Determine which player is always able to win the game and explain the winning strategy.
Solution
(a) Notice that for (a) $m$ and $n$ have greatest common divisor equal to 1 , therefore on each turn a player can always make a move of replacing the number $k$ with its divisor $l$ strictly less than $k$, as long as $l>1$, or as long as $l=1$ and 1 has not yet appeared on the board. Instead of dealing with the actual numbers we will deal with the number of prime factors they have. Then, the game becomes equivalent to the following. Two numbers $m$ and $n$ are written on the board. On each turn a player can select a number $k$ greater than 0 and replace it with any positive integer less than $k$, or replace it with 0 , as long as 0 is not already written on the board. A player who cannot make a move loses. It immediately follows that $m=0, n=1$ is a losing position. Therefore, $m=0, n \geq 2$ is a winning position (since a player replaces $n$ with 1 and wins). Furthermore, $m=1, n \geq 1$ is a winning position (since a player replaces $n$ with 0 and wins). Hence $m=2, n=2$ is a losing position; $m=2, n \geq 3$ is a winning position; $m=3, n=3$ is a losing position, $m=3, n \geq 4$ is a winning position. By induction it follows that for $k \geq 2, m=k, n=k$ is a losing position, while $m=k, n \geq k+1$ is a winning position.
We are in the case of $m=40, n=51 \geq 41$ in the "transformed" game, thus this is a winning position and Alphonse wins.
(b) This case is different, since now $m$ and $n$ have more than one divisor in common. We will deal with the original game and not make any transformations. Note that $m$ and $n$ are both powers of 2 , so throughout the whole game only powers of 2 can appear on the board.
We first note that the player who first writes down a number less than or equal to 2 loses. This is because if they write down 1 , then 2 has not yet been written; the opponent on the next turn replaces the other number with 2 wins. (Note that this move is legal since at the start $m>2, n>2$ so at the time that 1 is written, the other number on the board must be greater than 2 ). If they write down 2 , then 1 has not yet been written; the opponent on the next turn replaces the other number with 1 and wins.
Similarly, the player who first writes down a number less than or equal to 8 loses. This is because if they write down 4 , the other player writes 8 - thus forcing the original player
to write down a number less than or equal to 2 (note they cannot replace 8 with 4 since 4 has already appeared on the board). Similarly, if they write down 8 , the other player writes down 4 and wins.
By induction it follows that if $m, n>2^{2 k-1}$ then the player who first writes down a number less than or equal to $2^{2 k-1}$ loses for every positive integer $k$. Thus for the case $m=2^{40}, n=2^{53}$, the player to first write down a number less than or equal to $2^{39}$ loses. Therefore on his first turn, Alphonse replaces $2^{53}$ with $2^{41}$ and wins - because on her turn, Beryl is faced with $2^{40}$ and $2^{41}$ on the board and has to write down a number less than or equal to $2^{39}$.