1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – lulu
    Commented Mar 23, 2018 at 10:36
  • $\begingroup$ 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. $\endgroup$
    – lulu
    Commented Mar 23, 2018 at 10:44
  • $\begingroup$ 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. $\endgroup$
    – lulu
    Commented Mar 23, 2018 at 10:57

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .