Number of winning combination in Nim

Question

I am studying game theory and I am wondering how many winning combinations are possible for Nim game? Suppose, stones = 500 and piles = 5. With these number, there are many initial game positions are possible. like [1, 2, 4, 3, 490], [100, 100, 100, 100, 100], [100, 200, 100, 100], [0, 200, 200, 50, 50] and so on. So basically there are stones^piles combinations possible. Among these, some will yield Xor > 0 and considered as winning possible.

My question is - how many winning initial positions are possible for given stones and piles? Instead of checking all possible combinations(which is impossible for larger inputs), is there any smart way to solve this?

This is not a homework or programming contest problem.

Answer 1

I assume there are k piles and each pile can have stones in the range [0,n]. Then we can find the losing positions ( you can subtract from total to get no. of winning positions ) using dynamic programming. Let the number of bits in binary representation of n be b. We take a 2-D array called dp of size $kx2^b$, where dp[i][j] denotes number of ways of assigning no. of stones to first $i$ piles such that xor of no. of stones in these first $i$ piles is $j$. It is easy to see that no. of losing positions is dp[k][0]. Now what's left is to come up with the recurrence relation ( I leave the base cases for you to come up with ).

           // take care of the base case  
           for i in range 1 to k:
               for j in range 0 to 2^b:
                   dp[i][j] = 0
                   for m in range 0 to 2^b:
                       // first i piles have nim-sum j
                       // ... if first i-1 piles have nim-sum m in the last
                       // ... pile we keep (m xor j) stones
                       dp[i][j] = dp[i][j] + dp[i-1][m]

EDIT
If $k$ piles in total have $n$ stones , you can again solve it by dynamic programming , but this time keeping a 3-D dp array of size $k$x$2^b$x$n$, where dp[x][y][z] means number of arrangements of first x piles having in total z stones and the nim-sum being y. Although I point it out that this method would be feasible only for small values of $k$ and $n$ ( in the order of few hundreds ). Following is a pseudo code ( again take care of base cases, if you have problem with them you could comment )

            // take care of base cases
            // our answer would be ( no. of losing ) positions = dp[k][0][n]

            for i in range 1 to k:
                for j in range 0 to 2^b:
                   for l in range 0 to n:
                      dp[i][j][l] = 0
                      for m in range 0 to l:
                            dp[i][j][l] = dp[i][j][l] + dp[i-1][m^j][l-m]

Clearly the above method works for small $k$ and $n$ ( you can reduce the memory, which I leave up to you to figure out ).

Answer 2

(added) As I now realise, you are asking for the number when the total number of stones is given.

It seems to be easy to count the number of loosing positions when the maximum number of stones in each pile is a power of two (minus one). Remember that a postion is loosing if the nim-sum of all the piles is zero, that is xor-ing all the bits will give $0$ at each bit position. So if there are $k$ piles each with at most $2^n-1$ stones, for each bit position, half of the initial positions xor's to $0$. So for each of the $n$ bit positions there are $2^k$ possible combinations for the $k$ piles. Half of these, $2^{k-1}$ xor to zero. This is to be combined to for each bit position, so ${(2^{k-1})}^n$. The total number of initial positions is ${(2^{k})}^n$.

For an arbitrary number of stones there is not such a nice formula, I am afraid.