一维反Nim游戏

mathe

可以看出4□4先手胜，4□4□1先手负。
很有可能除去这两个状态后我前面贴出的方法成立，不过现在我还没能够验证

无心人

（1， 1， 1）负
（1， 1， 2）， （1， 1， 3）胜
（1， 2， 2）的子序列是
（1， 2）胜， （2， 2）负， （1， 1， 2）胜
所以（1， 2， 2）胜
同样（2，2，2）胜

无心人

（3， 4）子序列
（2， 4）胜，（1，4）胜，（3，3）胜，（2，3）胜，（1，1，4）负，（1，2，3）负
（1，1，4）子序列
（1，4）胜，（1，1，3）胜，（1，1，2）胜，（1，1，1，2）胜，（1，1，1，1）胜
（1，2，3）子序列
（2，3）胜，（1，3）胜，（1，1，3）胜，（1，2，2）胜，（1，1，2）胜，（1，1，1，2）胜

所以（3，4）胜

无心人

综合31# 41# 42# 43# 44#
9是先手负
所以10， 11先手胜
下一个是12

mathe

首先我们给一些更加方便的记号，比如
1*2+2*1可以简记为2+2*1(也就是所有1*可以省略),其次2*1也可以写成1*1+1*1=1+1

我们先考虑另外一个问题，其他规则都不变，但是允许拿最后一个子。轮到无子可拿的情况输（也就是拿到最后一颗的赢），对于这个情况，可以分析出一个比较好的结论，记:
s[1]=1
s[2]=2
s[3]=3
s[4]=1
s[5]=4
s[6]=3
s[7]=2
s[8]=1
s[9]=4
s[10]=2
s[11]=6
s[12]=4
s[13]=1
s[14]=2
s[15]=7
s[16]=1
s[17]=4
s[18]=3
s[19]=2
s[20]=1
s[21]=4
s[22]=6
s[23]=7
s[24]=4
s[25]=1
s[26]=2
s[27]=8
s[28]=5
s[29]=4
s[30]=7
s[31]=2
s[32]=1
s[33]=8
s[34]=6
s[35]=7
s[36]=4
s[37]=1
s[38]=2
s[39]=3
s[40]=1
s[41]=4
s[42]=7
s[43]=2
s[44]=1
s[45]=8
s[46]=2
s[47]=7
s[48]=4
s[49]=1
s[50]=2
那么对于一个局面$x_1+x_2+...+x_k$,这个局面的状态数为$s[x_1]^^s[x_2]^^...^^s[x_k]$
一个状态先手负的充要条件是其对应的状态数为0。

shshsh_0510

对于初始局势 1*n ,拿最后子赢的游戏简单的很，只需分为两个等长的序列就行了。但对任意初始局势的判定也挺复杂。

无心人

两位
9怎么判定的？能给我分析下么？
我怎么看9是输阿？

mathe

切换到本问题，我们可以知道，除了状态1*1和1*2以外，所有其他状态能够转移到的状态同上面一个问题完全相同。
我们对于某个状态s,记上一个问题中对应的状态数为g(s),这个问题中对应的状态数为f(s)
所以我们知道，如果对于某个状态s,它经过一次变换能够达到的所有不同状态为$s_1,s_2,...,s_h$
如果有$f(s_1)=g(s_1),f(s_2)=g(s_2),...,f(s_h)=g(s_h)$,那么我们必然可以有$f(s)=g(s)$。
而根据经验可以猜测除了少数状态以外，都会有$f(s)=g(s)$，我们的任务就是找出所有$f(s)!=g(s)$的状态s而且计算出其状态值.
第一步我们可以知道
$f(p*1)=0,f(o*1)=1$这两个状态不同于函数g,
所以所有可以到达p*1和o*1的状态都要重新计算状态数，也就是我们还需要计算状态
2+p*1,2+o*1,3+p*1,3+o*1,4+p*1,4+o*1
首先计算$f(2)=1!=g(2)=2$,所以,所有可以到达状态2的也需要重新计算，包括状态
3,4,2+1,2*2
其次计算$f(2+1)=2!=g(2+1)=3$
然后我们可以得到$f(2+p*1)=2!=g(2+p*1),f(2+o*1)=3!=g(2+o*1)$
所以所有可以到达这些状态的也都需要重新计算，也就是
2*2+p*1,2*2+o*1,3+p*1,3+o*1,4+p*1,4+o*1,5+p*1,5+o*1,3+2+p*1,3+2+o*1,4+2+p*1,4+2+o*1
加上前面列出的还需要添加状态3,4,2*2
都要重新计算

下一步需要计算2*2,2*2+o*1,2*2+p*1就是重复25#过程可以得到它们函数值同g函数值相同，所以不需要近一步考虑。
然后下一个需要计算状态3,3+p*1,3+o*1,3+2+p*1,3+2+o*1,根据27#的结果得到
$f(3)=2!=g(3)=3,f(3+p*1)=3!=g(3+p*1)=2,f(3+o*1)=2!=g(3+o*1)$
$f(3+2+p*1)=0=g(3+2+p*1),f(3+2+o*1)=1=g(3+2+o*1)$
也就是只有f(3),f(3+p*1),f(3+o*1)不同于g，为此我们还需要验证所有可以到达状态3,3+p*1,3+o*1的状态，包含状态
4,5,3+1,3+2,4+p*1,5+p*1,4+o*1,5+o*1,2*3+p*1,2*3+o*1,3+2+p*1,3+2+o*1,5,6,5+o*1,6+o*1,5+p*1,6+p*1
其中最大为3的已经验证和g函数相同，因此余下还有状态
4,4+p*1,4+o*1,4+2+p*1,4+2+o*1,5,5+p*1,5+o*1,6,6+p*1,6+o*1
已经得出所有不同项为
$f(p*1)=0,f(o*1)=1,f(2)=1,f(2+p*1)=2,f(2+o*1)=3,f(3)=2,f(3+p*1)=3,f(3+o*1)=2$,其余最大数不超过3的都同g相同
然后我们计算状态4,可以到达状态3,2,2+1,1+1;对应f状态值分别为2,1,2,1,所以$f(4)=0!=g(4)=1$
为此我们需要重新计算所有可以到达状态4的状态,包含状态6,5,4+1,4+2
其次计算4+1状态，可以到达状态4,3+1,2+1,2+2*1,3*1,所以对应f值为0,3,2,3,0
所以$f(4+1)=1!=g(4+1)=0$,所以我们需要重新计算6+1,5+1,4+2*1,6,7,4+2,4+3几个状态
4+2*1状态可以到达4+1,3+2*1,2+2*1,2+3*1,4*1,f值分别为1,2,3,2,1;所以得到$f(4+2*1)=0!=g(4+2*1)$
4+3*1状态可以到达4+2*1,3+3*1,2+3*1,2+4*1,5*1,f值分别为0,3,2,3,0;所以得到$f(4+3*1)=1!=g(4+3*1)$
同样可以得到4+o*1可以到达4+p*1,3+o*1,2+o*1,2+p*1,o*1,f值分别为1,2,3,2,1;所以得到$f(4+o*1)=0!=g(4+o*1)$
同样可以得到4+p*1可以到达4+o*1,3+p*1,2+p*1,2+o*1,p*1,f值分别为0,3,2,3,0;所以得到$f(4+p*1)=1!=g(4+p*1)$
到达它们的状态有5,6,5+o*1,5+p*1,6+o*1,6+p*1,7,7+o*1,7+p*1,4+2+o*1,4+2+p*1,4+3+p*1,4+3+o*1,2*4+o*1,2*4+p*1

到次我们已经知道同g不同的状态有
$f(p*1)=0,f(o*1)=1,f(2)=1,f(2+p*1)=2,f(2+o*1)=3,f(3)=2,f(3+p*1)=3,f(3+o*1)=2,f(4)=0,f(4+p*1)=1,f(4+o*1)=0$
需要继续计算的状态有
4+2,4+3,4+2+p*1,4+2+o*1,4+3+p*1,4+3+o*1,2*4+o*1,2*4+p*1,5,5+p*1,5+o*1,6,6+p*1,6+o*1,7,7+p*1,7+o*1
我们先查看状态4+2可以到达4,4+1,3+2,2*2,2*2+1,2+2*1,对应f值0,1,1,0,1,3;所以$f(4+2)=2!=g(4+2)$
到达4+2的状态有4+3,2*4,4+2+1,4+2*2,5+2,6+2,7,8
4+2+1可以到达4+2,4+2*1,4+1,3+2+1,2*2+1,2+3*1,2*2+2*1,对应f值2,0,1,0,1,2,0,所以$f(4+2+1)=3!=g(4+2+1)=2$
4+2+2*1可以到达4+2+1,4+3*1,4+2*1,3+2+2*1,2*2+2*1,2+4*1,2*2+3*1,对应f值为3,1,0,1,0,3,1;所以$f(4+2+2*1)=2!=g(4+2+2*1)=3$
同样我们可以得出$f(4+2+p*1)=3!=g(4+2+p*1)=2,f(4+2+o*1)=2!=g(4+2+o*1)=3$
计算4+2*2,可以到达4+2+1,4+2,3+2*2,3*2,3*2+1,2*2+2*1,对应f值3,2,3,2,3,0,所以$f(4+2*2)=1=g(4+2*2)$
类似估计其他4+x*2开头的都应该同g相同了。
其次计算4+3,可以到达4+1,4+2,4+2*1,2*3,3+2,3+2+1,3+2*1,对应f值为1,2,0,0,1,0,2;所以$f(4+3)=3!=g(4+3)$
4+3+1,可以到达4+3,4+2+1,4+2*1,4+3*1,2*3+1,3+2+1,3+2+2*1,3+3*1,对应f值3,3,0,1,1,0,1,3;所以$f(4+3+1)=2!=g(4+3+1)$
类似我们应该可以得到$f(4+3+o*1)=3!=g(4+3+o*1),f(4+3+p*1)=2!=g(4+3+p*1)$
然后查看4+3+2可以到达4+3+1,4+3,4+2*2,4+2+1,4+2+2*1,2*3+2,3+2*2,3+3*1,3+2+2*1对应f值2,3,1,3,2,2,3,3,1;
所以$f(4+3+2)=0=g(4+3+2)$.类似我估计后面的f值都应该同g值会相同了
也就是我们找出了同g值不同的f有

$f(p*1)=0,f(o*1)=1,f(2)=1,f(2+p*1)=2,f(2+o*1)=3,f(3)=2,f(3+p*1)=3,f(3+o*1)=2$
$f(4)=0,f(4+p*1)=1,f(4+o*1)=0,f(4+2)=2,f(4+2+p*1)=3,f(4+2+o*1)=2,f(4+3)=3,f(4+3+p*1)=2,f(4+3+o*1)=3$
对于其余的应该有$f(.)=g(.)$

mathe

状态9好像的确是先手输，前面分析还没有完，至少象f(2*4)我也没有分析到，这个计算一下又同g函数不同。不过如果得出f(9)=0,那么9以后的又会一堆同g函数不同，这种方法不能用下去了

mathe

不过感觉我上面的算法可以让计算机来做，那样会好很多，只是需要解决里面一些类似数学归纳法方法的问题
如得出f(2+p*1)=2,f(2+o*1)=3,两者需要互相以对方为基础，而且开始通常需要先计算f(2),f(2+1),f(2+2*1)等，然后再使用归纳法（而且可能少数情况这个规律不一定成立，这时需要多推导几项）