晓寒的小屋

随笔分类

随笔档案

相册

最新评论

阅读排行榜

评论排行榜

程序员博客   首页  新随笔  订阅  管理  登录 
 
晓寒 阅读(1181) 评论(6)
由于看到这篇blog描述的取小球推倒,觉得有误,故此论证一下。我看到的地方。
 游戏规则:
 1 游戏有甲,乙两个人, 有三排小球。第一排3个 第二排5个 第三排7个;
2 进行甲乙两人交替取走小球。
取小球遵循以下规则:
(1)每次可以取走任意多个小球;
(2)每次只能去走同一行中的小球;
3 取走最后一个小球的人为输。

当时我记得是如此取可以必胜,就是把堆里的数据,尽可能取2的次方。然后去掉相同的就可以了。
例如:
第一堆        第二堆             第三堆
3 = 2+1        4 = 4                5= 4+1 故变为
1= 1             4 = 4                5= 4+1 此时必胜。 再举一列
12 =8+4       14=8+4+2        18=16+2 因此应取为如下:
12 =8+4       14=8+4+2        2=2。

具体推论,偶也不知道,不过这个规律是正确的。 :P

评论列表
abcs
re: 关于取小球的误解。(由于是老问题,会做的就没有必要再看了)
特判全部是1的情况,此之外就全部异或起来,是0则必败,非0则必胜。利用维护异或值时0的办法可以构造必胜策略。
晓寒
re: 关于取小球的误解。(由于是老问题,会做的就没有必要再看了)
全部异或起来,是0则必败,非0则必胜?没有看明白。
abcs
re: 关于取小球的误解。(由于是老问题,会做的就没有必要再看了)
最基本的必胜态是偶数个1。考虑另外一种必胜态:除了一个大于1之外其它都是1(包括没有1的情况)。对于,利用xor可以证明,所有其它的必胜态都可以利用策略变成这种必胜态。证明的方法(也就是策略的构造)大致这样。考虑一个实例3,4,5,也就是011,100,101,xor起来是010。最高的非0位是bit1,那么3,4,5里面必然有一个数的bit1非0,是3。那么计算011 xor 010=001,所以应该从3这一堆里面取走3-1=2。
晓寒
re: 关于取小球的误解。(由于是老问题,会做的就没有必要再看了)
哈哈,你说的是比较规范的,而我解释的是很通俗的,就是2的倍数,然后互相抵消(就是xor了)。可是为什么这个状态是必胜态呢?能帮忙解释不?
abcs
re: 关于取小球的误解。(由于是老问题,会做的就没有必要再看了)
对总数用第二数学归纳法,证明方法可以仿照上面的实例,中间需要推一些简单的结论。
Davy
If only there were more cleevr people like you!

发表评论
切换编辑模式