2005-1-29 22:12
天痕
游戏A：
甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定。游戏的规则如下：
1。每一步应取走至少一枚石子；
2。每一步只能从某一堆中取走部分或全部石子；
3。果谁无法按规则取子，谁就是输家。
游戏B：
1。甲乙双方事先约定一个数m，并且每次取石子的数目不能超过m个；
2。其余规则同游戏A。
我们关心的是，对于一个初始局面，究竟是先行者（甲）有必胜策略，还是后行者（乙）有必胜策略。
请计算之
2005-1-29 23:25
潇湘暮客
老早就有类似的了
不难，但是不想想了
好像是第一个拿一个确定数
以后就跟乙的成某中关系
2005-1-29 23:33
月之魂魄
大航海时代4里费兰德的硬币游戏就属于第二个问题。m=3
记得当年打这的时候花了N长时间，汗。。。看来我智商有问题，怀疑ing....
2005-1-30 09:47
gunnarlin
1应该是二进制不进位加法
俺的奥数第一课
2就不知道了
2005-1-30 11:18
gunnarlin
2想了一下
先对每组石子按m+1取余
然后就是和1类似的判别方法了
综合下
1就是对所有的石子取二进制
然后作不进位加法，如果结果是全0，那么后手胜
不然 先手胜
2对所有的石子对m+1取余
然后把余数取二进制，结果同上
不知道对不对
2005-2-3 05:54
天痕
[quote]原帖由[i]gunnarlin[/i]于2005-01-30, 9:47:27发表
1应该是二进制不进位加法
俺的奥数第一课
2就不知道了 [/quote]
两个都对~~
不过请说明为什么可以这样做？
2005-2-3 11:51
gunnarlin
具体证明比较复杂，需要讨论各种情况（我想了下，应该不算很难)
就是按加（好像是那么说吧）的结果是全0和非0两种结果的互相切换
留给对手全0的局面就是必胜
反之必败存在一种取法能够给对方全0的局面（要分首位的情况，具体不讨论了）
对于m限制其实只要把每堆分为M+1的几组和尚上面1局面的石子
由于双方拿掉m+1不影响局面
所以就是这个结果了