0
$\begingroup$

Given $n$ piles of coins in a Nim game, how do I find the number of ways of making the first move under optimal play such that Player 1 always wins?

$\endgroup$
1
$\begingroup$

The complexity is $O(n)$ - you can compute the nim-value $p$ of the position as a whole, then nim-sum that with each of the column values $\{c_i: i\leq n\}$. The valid (winning) first moves are exactly the ones for which $c_i\oplus p\lt c_i$. (Note that you can't have $c_i\oplus p=c_i$ unless $p=0$, in which case there are no winning moves for the first player). What's more, since just computing $p$ is $O(n)$ (you have to look at all the data), you can't really do any better than this. (Though parallel algorithms are another story — I don't know what the complexity is in a PRAM model, for instance.)

$\endgroup$
  • $\begingroup$ Can you please provide a proof or reasoning for the condition $c_i\oplus p\lt c_i$? Is it because we are making the heap more balanced from an unbalanced position? Sorry, but I am new to Nim games. $\endgroup$ – xennygrimmato Jul 18 '14 at 4:15
  • $\begingroup$ @rayu after any move $c_i\mapsto c_i'$, the value of the new position is $p\oplus c_i\oplus c_i'$ (this is because we 'remove' $c_i$ from the position and replace it with $c_i'$). This is zero (i.e., the initial move was a winning one) iff $p\oplus c_i\oplus c_i'=0$ iff $c_i' = p\oplus c_i$ (again, using that $x\oplus x=0$ for all $x$). That $p\oplus c_i\lt c_i$ is then just the condition for the move to be legal - that is, to leave fewer coins in that pile than it started with. $\endgroup$ – Steven Stadnicki Jul 18 '14 at 4:31

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.