14
$\begingroup$

Alice and Bob play a game with a pile of $n$ pebbles. They take turns, with Alice going first. On their turn, a player can remove any number of stones from the pile which is a proper divisor of the size of the pile on that turn. If a player reduces the pile to a single pebble, they win.

For which values of $n$ does Alice win under optimal play?

For example, if $n=12$, Alice's first move could be to remove $1,2,3,4$ or $6$ stones. Suppose she removes $2$ (this is a legal move, not necessarily an optimal one). Bob now faces a pile of $10$ pebbles, from which he can remove $1,2$ or $5$ stones.

Improve this question
$\endgroup$
2
  • $\begingroup$ Interesting variant of Nim! $\endgroup$
    – Rand al'Thor
    Commented May 25, 2015 at 8:40
  • $\begingroup$ Very simple, but clever, impartial game; it makes it easy to understand why in Nim you can always determine the winning move in advance(if there is one), no matter how many moves are left... $\endgroup$
    – SilverCookies
    Commented Jul 2, 2018 at 12:43

1 Answer 1

Reset to default
11
$\begingroup$

Alice wins if and only if

$n$ is even.

Proof

By induction. Firstly, $n=2$ is obviously a winning position, while $n=3$ is a losing position because the only allowed move is to remove one pebble, leaving the winning position $n=2$ for Bob.

Now assume that for all $n<2N$, $n$ is a winning position if and only if $n$ is even. Now $n=2N$ is a winning position since Alice can remove a single pebble leaving Bob with the odd (therefore losing, by the induction hypothesis) position $2N-1$. And $n=2N+1$ is a losing position since any factor of this odd number is odd and so Alice would have to leave Bob with an even (therefore winning, by the induction hypothesis) position $2k\leq2N$.

QED.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't follow this. Take the example in the question, they start with 12 which is even. So Alice is going to win. She removes 2 leaving 10. This is the same as starting with 10 (which is even) and Bob going first. So Bob is going to win? Or is the "optimal play" that Alice must choose a number of stones to remove that leaves Bob with an odd number? $\endgroup$
    – Kate Gregory
    Commented May 25, 2015 at 11:50
  • $\begingroup$ @KateGregory Alice keeps making it an odd number for Bob (i.e subtract 1), then Bob must then make it even again for Alice (since he can't take all the pebbles, and there is no odd number whose divisor when subtracted will have another odd number). Eventually Alice will make it equal to 3 then 1 (odd) to which Bob losses. $\endgroup$
    – Mark N
    Commented May 25, 2015 at 13:28
  • $\begingroup$ I understand the question only asked what n was given optimal play, but it seems to me that a simple definition of that optimal play belongs in the answer, especially since non-optimal play is provided as an example in the question. $\endgroup$
    – Kate Gregory
    Commented May 25, 2015 at 13:31
  • 2
    $\begingroup$ @KateGregory Optimal play is defined recursively as follows. 1) n=1 is (in this game) a losing position by definition. 2) A position is winning if there exists a single move from it that gets to a losing position. 3) A position is losing if every single move from it gets to a winning position. $\endgroup$
    – Rand al'Thor
    Commented May 25, 2015 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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