Multi-nim结论及证明

考虑有这样一种nim游戏，每次可以取石子或把一堆石子分为两堆都不为0的石子，最后取完的获胜。

先给出结论，(Sg(x))表示一堆石子数为(x)的sg值

[Sg(x)=egin{cases} 0(x=0)\ x-1(xmod4=0)\ x(xmod4=2,1)\ x+1(xmod4=3)\ end{cases}]

然而我并没有找到严谨的证明，大家好像都是通过暴力算sg函数然后打表找规律的方法得到的，那我给出一种证明（不一定严谨QAQ）

考虑用数学归纳法：

对于(x=0,1,2,3)，上式显然成立

然后我们对(x)分情况讨论：

1. (xmod4=1iff x=4a+1)

(Sg(x))是所有后继的mex，那么我们只需要考虑(x)前几个数的sg值

(Sg(4a)=4a-1,Sg(4a-1)=4a,Sg(4a-2)=4a-2,Sg(4a-3)=4a-3=4(a-1)+1)

因为(x)可以拆成(x-y,y)的形式，所以我们还要考虑(Sg(x)oplus Sg(x-y))

通过对(x,x-y)大力分情况讨论可以发现(Sg(x)oplus Sg(x-y))无法得到(4a+1)，那么该情况成立

2. (xmod4=2iff x=4a+2)

我们仍然考虑sg值

(Sg(4a+1)=4a+1,Sg(4a)=4a-1,Sg(4a-1)=4a,Sg(4a-2)=4a-2=4(a-1)+2)

同样按照上面的方法分析可以发现(Sg(x)oplus Sg(x-y))无法得到(4a+2)，于是该情况成立

3. (xmod4=0iff x=4a)

(Sg(4a-1)=4a,Sg(4a-2)=4a-2,Sg(4a-3)=4a-3,Sg(4a-4)=4a-5=4(a-1)-1)

同理(Sg(x)oplus Sg(x-y))无法得到(4a-1)，该情况成立

4. (xmod4=3iff x=4a+3)

(Sg(4a+2)=4a+2,Sg(4a+1)=4a+1,Sg(4a)=4a-1,Sg(4a-1)=4a)

而这次我们可以构造出(y=3,x-y=4a)得到(Sg(y)oplus Sg(x-y)=3oplus 4a=4a+3)，因为(4a)二进制最后两位一定为(0)，所以和(3)异或等同于加法，而且通过和上面类似的讨论可以发现(Sg(x)oplus Sg(x-y))无法得到(4a+4)，于是该情况成立

综上四种情况都成立那么该结论成立。

暂时还不知道数学归纳以外的证法QAQ