Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?
share|cite|improve this question

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.