# Replace number by non-divisor

Two players take turns playing a game where they start with a positive integer $n$. Each player must replace the existing number by a smaller positive integer that is not its divisor. Whoever cannot do this loses. For which $n$ does the first player have a winning strategy?

If $n=1$ or $2$, the first player loses immediately. For all other $n$, the first player can make at least one move. If $n\geq 3$ is odd, the first player can win by replacing the number with $2$. On the other hand, if $n$ is even, the first player cannot immediately win.

$n=4$: first player must replace by $3$ and loses.

$n=6$: first player can replace by $4$ and win.

$n=8$: no matter whether first player replaces by $3$, $5$, $6$, or $7$, he loses.

$n=10$: first player can replace by $4$ and win.

$n=4r+2$: first player can replace by $4$ and win.

• The usual way to start on problems like this is to write out winners and losers for small $n$ and see if you can spot a simple pattern.
– lulu
Commented Mar 23, 2018 at 10:36
• Ok...so the pattern is pretty clear, no? I mean, the losers are $\{1,2,4,8,\cdots\}$ so... Now you just have to prove it.
– lulu
Commented Mar 23, 2018 at 10:44
• Note: I read the rules as saying that, handed $n$, you could name any $m<n$ which did not divide $n$. Indeed, your example of $n=10.m=4$ would appear to confirm my reading...but you should clarify.
– lulu
Commented Mar 23, 2018 at 10:57

The losers are numbers of the form $2^n$. We can show this by induction.
If the starting number is of the form $2^n$, the first player must change it to a non power-of-two and therefore loses.
If the starting number is not of the form $2^n$, suppose it is $2^n\cdot r$ for some odd $r\geq 3$. The first player can change to $2^{n+1}$ and win.