Anselmo and Bonifacio start a game where they alternatively substitute a number written on a board. In each turn, a player can substitute the written number by either the number of divisors of the written number or by the difference between the written number and the number of divisors it has. Anselmo is the first player to play, and whichever player is the first player to write the number $0$ is the winner. Given that the initial number is $1036$, determine which player has a winning strategy and describe that strategy. Note: For example, the number of divisors of $14$ is $4$, since its divisors are $1$, $2$, $7$, and $14$.
Problem
Source: 2015 CentroAmerican Math Olympiad #4
Tags: OMCC, combinatorics
01.07.2015 00:43
For any given $n \ge 0$ let $d(n)$ be the number of divisors of $n$. So players have 2 options each turn, replace $n$ with $d(n)$ or $n-d(n)$. Obviously $1 \le d(n) \le n$, so $n-d(n) < n$. If $d(n)=n$ (which only happens for $n=1,2$), then the player who'se turn it is can win immediatly by replacing that $n$ with 0. So for $n=1,2$ the game is won by the player who'se turn it is and for all bigger n he has to replace it with a number smaller than n. So we can easily (in theory) find out who wins when presented with a given number by first finding out who wins when presented with 3, then who wins when presented with 4, a.s.o until we reach the given number. A player where both options $d(n)$ and $n-d(n)$ are winners for the player who is presented with them will be a looser, but a player where at least one of the options $d(n)$ and $n-d(n)$ is a loosing number is itself a winner. Fortunately, we don't have to do this manually until 1036, doing until 12 proves to be enough. A player presented with 1 or 2 wins (denoted by 1W, 2W), the player presented with 3 has the 2 options to substitute the 3 with a 1 or a 2, so he looses. One can very easily continue this: 1W, 2W, 3L, 4W, 5W, 6L, 7L, 8L, 9W, 10W, 11L, 12W. Now, we have $1036=2*2*7*37$ as the prive factorization of 1036 and hence $d(1036)=12$. Anselmo (first player) has to choose between putting 12 or 1024 on the board. As we saw above, 12 would be a winning number for Bonifacio, so to have a chance Anselmo has to put the 1024 on the board. Since $1024=2^{10}$ we have $d(1024)=11$, so Bonifacio has to choose between 11 and 1013. 11 is a loosing number, so he will choose it and make Anselmo loose. So no matter what Anselmo does, he will always loose if Bonifacio plays well.