数学研发论坛

 找回密码
 欢迎注册
楼主: medie2005

[转载] 棋子游戏

[复制链接]
发表于 2008-9-11 14:54:43 | 显示全部楼层
我倒是觉得这个题目本来就挺复杂的,要用计算机才行,手工太复杂了.
有点好奇,shshsh为什么用pi代替奇数,oi代表偶数,o可以解释为偶数的拼音,p呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-11 15:21:37 | 显示全部楼层
其实这个还是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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-11 15:21:55 | 显示全部楼层
呵呵,一会用jo,一会用pe,难免不会用po,je
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-11 15:37:54 | 显示全部楼层
上面汇总有
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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-11 15:46:16 | 显示全部楼层
进行结果填充吧
看能分析到多大的结果
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-11 16:06:31 | 显示全部楼层
下一步看状态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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-11 16:15:49 | 显示全部楼层
呵呵f(2*3)=0,f(2*3+1*1)=4第一个出现4的,后面越来越复杂了,不借助计算机很难算下去
不过已经可以知道7先手赢了,拆成两个3就可以了.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-11 16:55:57 | 显示全部楼层
假设m, n能先手赢,则能拆成(m, n)的是否一定先手赢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-11 16:57:11 | 显示全部楼层
那也能确定8是先手赢,也能拆成(3, 3)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-11 16:59:16 | 显示全部楼层
9很显然,不能从两边拿

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

备注(1, 1, 4), (1, 2, 3)均负
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-8-22 00:28 , Processed in 0.055408 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表