Alice and Bob play the following game. They choose a number $N$ to play with. The rules are as follows:
- Alice plays first, and the two players alternate.
- In his/her turn, a player can subtract from $N$ any proper divisor (not equal to $N$) of $N$. The number thus obtained is the new $N$.
- The person who cannot make a move in his/her turn loses the game.
Assuming both play optimally, who wins the game ?
Best Answer
You can show by induction:
$N=1$ is a losing position as there is no move.
$N>1$ and even is a winning position: you can subtract an odd proper divisor such as $1$ to reach an odd number
$N>1$ and odd is a losing position: you must subtract an odd proper divisor to reach an even number