Number of ways in a Nim game such that First Player always wins

Question

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?

Answer 1

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.)