Given a number $N$:
- Two people A and B subtracts a number k
$\left(~0 < k < N,\ k\mid N~\right)$ alternatively from $N$. - The one who cannot make a move loses the game.Provided that A always starts first, decide the winner.
Initially, I tried solving this problem using dynamic programming considering the fact that a state can be a winning one if it leads to at least one losing state. Also, a state is a losing one if all the states it goes to are winning. Checking for all the states didn't prove to be time efficient. After looking at the solutions I found that this problem boils down to checking whether N is odd or even. What I think is, one can say that if a state X is losing then $\mathbf{X + 1}$ $\left(\,\mbox{as}\ \mathbf{1\mid\left(\,X + 1\,\right)}\,\right)$ will always be a winning state but what if $\mathbf{X}$ is a winning state ?.
How can one prove that even states will always be winning and vice versa ?.
Best Answer
Note a few things:
1) If you are passed an even number, you can not be made to lose in that turn.
This is because $N = 2m > 1$ and $1|N$ so you can pass $N -1$.
2) If you are passed an odd number, then either a) you are forced to lose if $N =1$ or b) you are forced to pass an even number. And your opponent cannot be made to lose in the next turn.
a) if $N =1$ you can't do anything.
b) if $N > 1$ but $N$ is odd so if $k|N$ then $k$ is odd and you must pass $N -k$ which is an odd minus an odd must be even.
3) if you are passed an even you can make it so that you are passed an even the next turn (if there is a next turn).
Just pass the $N-1$. That will be odd and your opponent must pass you an even by 2). (or the opponent must lose if you passed a $1$). [If you have a larger odd $k$ that divides $N$ you can pass $N -k$ which will also be odd. That will speed the game up.]
4) The game is finite and must end.
You are passed a finite $N$ and you pass an $1 \le N - k < N$ that is smaller. There are only a finite number (maximum $N$) turns that can be taken.
...... so ......
So if you are passed an even you need not lose that turn or, by induction, any other turn. If you are passed an odd you might lose but you can not make your opponent lose. All games must end.
Therefore (if both players play the best strategy) player $A$ will lose if the first $N$ is odd. Player $A$ will win if the first $N$ is even.