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?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.)
answered Jul 18, 2014 at 3:55
-
$\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$– rayuJul 18, 2014 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$ Jul 18, 2014 at 4:31