Sprague-Grundy Theory

Theorem: If G = g1+g2, then sg(G) = sg(g1)^sg(g2)

Proof:
Base case: If sg(g1) = sg(g2) = 0, then G is a P position, which has sg value 0 = 0^0

Induction: We have to prove
1. If sg(G) = v, then sg(G') != v if G → G'
2. If x < sg(G), then there exists G' where G → G' and sg(G') = x

Part 1
Assume G = g1+g2. WLOG, let G' = g1' + g2, by definition, sg(g1) != sg(g1')
Hence sg(G) = sg(g1)^sg(g2) != sg(g1')^sg(g2) = sg(G')

Part 2
Assume sg(g1) = A, sg(g2) = B, sg(G) = C and A < B
If we write A and B in binary representation, we have

A = an an-1 ... 1 ... a2 a1
B = bn bn-1 ... 0 ... b2 b1

and the bits of A,B before the 1 and 0 are same.

Let x < C. Consider x^sg(g2), we have

  C = cn cn-1 ... 1 ...
  x = cn cn-1 ... 0 ...
x^B = an an-1 ... 0 ...

Hence x^B < A. By definition, there exists g1' where sg(g1') < sg(g1) and sg(g1') = x^B.
Assume G' = g1'+g2, we have sg(G') = sg(g1')^sg(g2) = x^B^B = x.
Therefore G' exists.