2
$\begingroup$

A position in Nim consists of some piles of coins. Two players alternate, with each move removing a portion of one pile. The winner is the player who takes the last coin.

Suppose that the starting piles have size $n_1,...,n_k$. Prove that Player 2 has a winning startegy if and only if for every $j$, an even number of $n_1,...,n_k$ have a $1$ in position $j$ in their binary representation. For example, when the sizes are $1,2,3$, the binary representation are $1, 10, 11,$ and the condition holds.

$\endgroup$
1
  • 1
    $\begingroup$ Have you even read the Wikipedia article on Nim?! $\endgroup$
    – kahen
    Jul 18, 2011 at 10:23

1 Answer 1

Reset to default
6
$\begingroup$

This is a well known result. Surely you can google up something, or failing that, go to a math library and read a solution from "Winning Ways I-II" by Berlekamp, Conway and Guy.

But I'm glad to hear that you want to work it out yourself. Here are a couple of hints. Call a position in the game of Nim balanced, if the sequence of numbers of remaining coins in the piles satisfies the condition "even number of 1s in any position", and call it unbalanced otherwise.

1) Show that if a player is given a balanced position, then any move s/he will make leaves an unbalanced position.

2) Show that if we are given an unbalanced position, there exists a move (at least one, possibly more) that will leave the other player with a balanced position.

3) Note that the desired all-zeros end position is balanced. Apply a little bit of recursive thinking (or induction, if you like).

$\endgroup$
4
  • 1
    $\begingroup$ "glad to hear..." -? It sounds like he wants us to work it out! $\endgroup$
    – The Chaz 2.0
    Jul 18, 2011 at 13:17
  • 3
    $\begingroup$ @The Chaz: Given that the OP didn't just use a Wikipedia article or some such, my inner optimist wants to hang on to a positive world view. The role of the teacher is to inspire! </tongue-in-cheek> $\endgroup$
    – Jyrki Lahtonen
    Jul 18, 2011 at 13:24
  • 1
    $\begingroup$ My browser didn't complie the tongue in cheek! Regardless, I appreciate your optimism $\endgroup$
    – The Chaz 2.0
    Jul 18, 2011 at 16:11
  • $\begingroup$ Sorry if it came off as me asking for the answer. It sort of was. I was stuck on a problem and you pointed me in the right direction, I'm thankful for that. $\endgroup$
    – rapidash
    Jul 21, 2011 at 22:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .