# Nim Variant (reducing by divisors)

Alice and Bob play the following game. They choose a number $N$ to play with. The rules are as follows:

1. Alice plays first, and the two players alternate.
2. 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$.
3. The person who cannot make a move in his/her turn loses the game. Assuming both play optimally, who wins the game ?
-

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

-
The only real need for induction is to show that the game terminates; it’s clear that the even and odd positions have the characteristic relationship of N- and P-positions. (That was a quick solution!) –  Brian M. Scott Sep 11 '12 at 19:24