Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|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

 
discard

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.