A positive integer is written on a blackboard. Players $A$ and $B$ play the following game: in each move one has to choose a proper divisor $m$ of the number $n$ written on the blackboard ($1<m<n$) and replaces $n$ with $n-m$. Player $A$ makes the first move, then players move alternately. The player who can't make a move loses the game. For which starting numbers is there a winning strategy for player $B$?
Problem
Source: 2013 Baltic Way, Problem 7
Tags: induction, strong induction, combinatorics unsolved, combinatorics
31.12.2013 11:02
Let us call protected a number $n$ such that the player who plays has a winning strategy. We claim the protected numbers are $n=2^{2k}$ with $k$ positive integer, and $n=2^{k}\ell$ with $k,\ell$ positive integers and $\ell>1$ odd. We prove this by strong induction on $n$; the small (starting) cases are easy to check. $\bullet$ For $n=2^{2k}$, the player playing chooses $m=2^{2k-1}$, leaving $n-m=2^{2k-1}$, an odd power of $2$. $\bullet$ For $n=2^{k}\ell$, the player playing chooses $m=\ell$, leaving $n-m=(2^{k}-1)\ell$, an odd positive integer. Therefore $B$ has a winning strategy if and only if the starting number $N$ is unprotected, i.e. $N$ is odd, or is an odd power of $2$.
27.06.2020 14:28
Call a number to be a "winning position" if when a player is faced with the number, he can guarantee a winning position . Call a number to be a "losing position" if the next player can force a win . Claim : $n$ is winning iff $n$ is even and not a odd power of $2$. Proof Use strong induction on $n$ . Consider the cases := (i)Suppose a player is faced with an odd number $n$. Then they must subtract an odd divisor $d$, so $n$-$d$ is even. Moreover, $n$-$d$ is divisible by $d$, so it is not a power of $2$. Thus by induction hypothesis $n$-$d$ is winning for their opponent. (ii) Suppose a player is faced with $n = 2^{2k+1}$. Then they must subtract an even divisor d to get the even number $n$-$d$, which is not an odd power of $2$ (it is a power of $2$ only if $d = 2^{2k}$ , but then $n$-$d = 2^{2k}$. Thus by induction hypothesis $n$-$d$ is winning for their opponent. (iii) Suppose on the other hand a player is faced with $n = 2^{2k}$. They may choose $d$= $2^{2k-1}$ so $n$−$d$= $2^{2k-1}$ is losing for their opponent by induction hypothesis. (iv)Finally, suppose a player is faced with an even $n$ which is not a power of $2$. Then they may subtract some odd divisor $d$ , to get an odd number $n$−$d$ which is losing for their opponent. Done . Therefore $B$ has a winning strategy if and only if $N$ is odd, or is an odd power of $2$.