3
$\begingroup$

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 ?

2 Answers 2

8

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

  • 1
    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!)2012-09-11