Sprague Grundy theorem

The theorem is about sum of several nim games. A nim game is a pile of stones and in each turn you can take 1 to n stones. The last one makes a move wins.

One pile is trivial, two pile is not hard, what if you have 3 or more piles?

The nim game is solved by the notion of P-position and N-position. A P-position is a configuration, in this case, the number of stones in each pile, such that the previous player wins. An N-position is a configuration that the next player wins.

1. Terminal position is P-position.

2. If a position can go to a P-position, then it is an N-position.

3. If all next positions are N-position, then it is a P-position.

The Bouton's theorem says that a nim game is a P-position iff the nim sum, that is, the xor of all pile size, is 0. Proof by induction. The terminal configuration (0,0,...0) is a P-position. For a general configuration (x1, x2, ..., xn), if its nim-sum is 0, then any move will lead to a configuration with nim-sum nonzero. If its nim-sum is nonzero, then we show that there is a move to a next configuration with nim-sum zero. The move? if x1 + x2 + ... + xn (here + is xor) is nonzero, then there is a leftmost bit that  has odd number of xi with that position bit = 1. To make the sum zero, we have to remove that 1, and complement the sum of other x_j. This can always be done because the complement is smaller than x_i. It turns out the number of moves is exactly the number of x_i with bit = 1 at that position, and there are an odd number of them.

A generalization of the nim game is a graph game with each node having an edge to its successors. Then the P- and N-position is generalized to a much more powerful concept of Sprague-Grundy function, sg(x), defined as the smallest missing nonnegative integer of the set of sg(y) values, where y is a next configuration of x.

The theorem says that x is a P-position iff sg(x) = 0.

We can check the following:

1. sg(x) = 0 when x is a terminal position.

2. If sg(x) = 0, then any move to next configuration results in sg(y) > 0 (because sg(x) cannot be 0 if any sg(y) is 0)

3. If sg(x) > 0, then there must be a next configuration y such that sg(y) = 0 (otherwise sg(x) will be 0)

Now the sum of graph games.

If x is a nim-game consists of n components, x1, ..., xn

sg(x) = sg(x1) + sg(x2) + ... + sg(xn)

again the + is nim-sum, also known as xor.

Why? The proof is very similar to the previous one.

1. terminal configuration, when x has no move, then none of x1, ... xn has a move, and sg(x) = 0

as well as sg(x1) = ... = sg(xn) = 0

2. Now we go from x1, x2, ... xn to a next configuration.

Let b = sg(x1) + sg(x2) + ... + sg(xn)

we are to show two things

i) no next configuration y can have sg(y) = b

ii) for every nonnegative integer a < b, there exists a move of x_i to y_i such that sg(y) = a

First we prove i). Any x_i will move to y_i and we know that sg(x_i) != sg(y_i). Therefore sg(y_i) + sg(x_1) + ... + sg(x_i-1) + sg(y_i) + sg(x_i+1) + ... + sg(x_n) != b.

Second we show that for any a < b, we have a move for some x_i to y_i such that sg(x_1) + ... + sg(y_i) + ... + sg(x_n) = a. The hard part here is that we can move only one x_i.

Since a < b, then we can find some leftmost bit such that b has 1 and a has 0. Let d = a + b, again nim-sum (xor), If our move changes sg(x_i) to sg(x_i) + d, then the resulting configuration, applying inductive hypothesis, will give us sg(x_1) + ... + sg(x_i) + d + ... + sg(x_n) = b + d = a.

Since b has a left bit with 1 while a has that bit as 0, and b is sum of sg(x_i), then there exists some x_i such that sg(x_i) has 1 at that bit too. Since both d and sg(x_i) has that bit as 1, the sum d + sg(x_i) will have that bit as 0. The reason x_i has its SG value being g(x_i) is that x_i has a move to some y_i such that sg(y_i) = t for every t = 0, ... g(x_i) -1. So we must have a move from x_i to y_i such that sg(y_i) = d + g(x_i). And we are done.

The key in this proof is to keep in mind that the reason x_i has value sg(x_i) implies it has a move to y_i such that sg(y_i) = a for every a < sg(x_i). Also we are looking for a way to reset one bit to zero. The rest is just induction.

The Sprague-Grundy function is very powerful and was able to handle a large range of sum of impartial games.

The above was from the UCLA notes
http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf
and motivated by
http://codeforces.ru/contest/256/problem/C?locale=en