一维反Nim游戏

mathe

我倒是觉得这个题目本来就挺复杂的,要用计算机才行,手工太复杂了.
有点好奇,shshsh为什么用pi代替奇数,oi代表偶数,o可以解释为偶数的拼音,p呢?

mathe

其实这个还是Nim游戏的变种,只是挺复杂的.
还是采用shshsh的记号,用pi表示奇数个i,oi表示偶数个i吧.
不过有时候我们可能会需要一些特例,比如模式{1个2}和{1个2,2个1}都是p2o1
但是前者可以同时用p2表示,所以如果模式p2也同时出现,那么它优先(也就是小的模式优先)匹配
同样如果p2和{1个2}同时出现,那么{1个2}是一个特例,它的匹配优先级最高.
不过{1个2}这种形式写着不舒服,我们改用记号1*2,同样pi用p*i来表示.而同样我们可以有复合状态比如奇数个2一个1可以写成p*2+1*1
我们首先知道,奇数个1都是先手输局面,所以我们知道对应的Nim函数有
f(p*1)=0
而对于任何一个o*1,我们只能选择去掉一个1从而达到p*1状态,也就是只能转移到对应Nim函数值为0的状态,所以
f(o*1)=1
然后我们查看状态1*2,由于不能拿最后一个子,只能到达状态1*1,对应Nim函数值为0,所以同理
f(1*2)=1
然后我们查看状态1*2+1*1,它可以到达状态2*1,1*1,1*2,也就是可以转移到Nim函数值0,1,所以
f(1*2+1*1)=2
然后我们可以得出f(1*2+p*1)=2,f(1*2+o*1)=3

shshsh_0510

呵呵，一会用jo,一会用pe，难免不会用po，je

mathe

上面汇总有
f(p*1)=0,f(o*1)=1,f(1*2)=1,f(1*2+p*1)=2,f(1*2+o*1)=3
然后查看2*2,可以到达1*2,1*2+1*1,Nim函数值0没有取到,所以f(2*2)=0
2*2+1*1可以到达2*2,1*2+2*1,1*2+1*1,Nim函数值1没有取到,所以f(2*2+1*1)=1
2*2+2*1可以到达2*2+1*1,1*2+3*1,1*2+2*1,所以f(2*2+2*1)=0
由此我们可以归纳证明f(2*2+o*1)=0,f(2*2+p*1)=1
同样3*2可以到达2*2,2*2+1*1,所以f(3*2)=2
3*2+1*1可以到达3*2,2*2+2*1,2*2+1*1,所以f(3*2+1*1)=3
同样f(3*2+2*1)可以到达3*2+1*1,2*2+2*1,2*2+3*1,所以f(3*2+2*1)=2
归纳得到f(3*2+p*1)=3,f(3*2+o*1)=2
然后进一步我们可以得到f(o*2+o*1)=0,f(o*2+p*1)=1,f(p*2+p*1)=3,f(p*2+o*1)=2
到此总结结果为:
f(p*1)=0,f(o*1)=1,f(1*2)=1,f(1*2+p*1)=2,f(1*2+o*1)=3
f(o*2+o*1)=0,f(o*2+p*1)=1,f(p*2+p*1)=3,f(p*2+o*1)=2

无心人

进行结果填充吧
看能分析到多大的结果

mathe

下一步看状态1*3,由于一个3可以变成1个1,1个2或两个1
所以1*3可以到达1*1,1*2或2*1,查询上面结果知道可以达到0,1所以
f(1*3)=2
然后1*3+1*1可以到达2*1,1*2+1*1,3*1,得到
f(1*3+1*1)=3
然后1*3+2*1可以到达3*1,1*2+2*1,4*1,得到
f(1*3+2*1)=2
1*3+p*1可以到达o*1,p*1,1*3+o*1
f(1*3+p*1)=3
1*3+o*1可以到达p*1,o*1,1*3+p*1
f(1*3+o*1)=2

1*3+1*2可以到达2*2,1*2+1*1,1*2+2*1,1*3,1*3+1*1{0,2,3,2,3}
f(1*3+1*2)=1
1*3+1*2+1*1可以到达2*2+1*1,1*2+2*1,1*2+3*1,1*3+1*1,1*3+2*1,1*3+1*2{1,3,2,3,2,1}
f(1*3+1*2+1*1)=0
1*3+1*2+2*1可以到达2*2+2*1,1*2+3*1,1*2+4*1,1*3+2*1,1*3+3*1,1*3+1*2+1*1{0,2,3,2,3,0}
f(1*3+1*2+2*1)=1
1*3+1*2+p*1可以到达2*2+p*1,1*2+o*1,1*2+p*1,1*3+p*1,1*3+o*1,1*3+1*2+o*1{1,3,2,2,3,1}
f(1*3+1*2+p*1)=0
1*3+1*2+o*1可以到达2*2+o*1,1*2+o*1,1*2+p*1,1*3+p*1,1*3+o*1,1*3+1*2+p*1{0,3,2,2,3,0}
f(1*3+1*2+o*1)=1

1*3+2*2可以到达3*2,2*2+1*1,2*2+2*1,1*3+1*2,1*3+1*2+1*1{2,1,0,1,0}
f(1*3+2*2)=3
1*3+2*2+1*1可以到达3*2+1*1,2*2+2*1,2*2+3*1,1*3+1*2+1*1,1*3+1*2+2*1,1*3+2*2{3,0,1,0,1}
f(1*3+2*2+1*2)=2
1*3+2*2+o*1可以到达3*2+o*1,2*2+p*1,2*2+o*1,1*3+1*2+o*1,1*3+1*2+p*1,1*3+2*2+p*1{2,1,0,1,0,2}
f(1*3+2*2+o*1)=3
1*3+2*2+p*1可以到达3*2+p*1,2*2+o*1,2*2+p*1,1*3+1*2+p*1,1*3+1*2+o*1,1*3+2*2+o*1{3,0,1,0,1}
f(1*3+2*2+p*1)=2
好像可以归纳为
f(1*3+p*2+p*1)=0
f(1*3+p*2+o*1)=1
f(1*3+o*2+p*1)=2
f(1*3+o*2+o*1)=3

mathe

呵呵f(2*3)=0,f(2*3+1*1)=4第一个出现4的,后面越来越复杂了,不借助计算机很难算下去
不过已经可以知道7先手赢了,拆成两个3就可以了.

无心人

假设m, n能先手赢，则能拆成(m, n)的是否一定先手赢？

无心人

那也能确定8是先手赢，也能拆成(3, 3)

无心人

9很显然，不能从两边拿

所以必须考虑拆成两个部分
(1, 7)胜
(2, 6)胜
(3, 5)胜
(4, 4)胜
(1, 6)胜
(2, 5)胜
(3, 4)胜

备注(1, 1, 4), (1, 2, 3)均负