2
$\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 ?
$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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!) $\endgroup$ – Brian M. Scott Sep 11 '12 at 19:24
1
$\begingroup$

If $N$ is an even number then Alice wins otherwise Bob wins.

If the player is on an even number, he/she will subtract 1 from the number.The opponent will then have an Odd number, and all factors of odd numbers are Odd, hence he can only subtract an Odd numbe, hence player will again get an even number on his/her chance. What will remain invariant is that current player will always have an even number and the opponent will have an odd number.This process will keep continuing until they reach one of the numbers between 1 and 8, for which the result is given above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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