魔方吧·中文魔方俱乐部

标题: 一个有趣难解的游戏 [打印本页]

作者: hubo5563 时间: 2010-8-16 22:13:22 标题: 一个有趣难解的游戏

开始有三堆不等的石子，分别假定为n1，n2，n3。两个人轮流抓，规则如下：
轮到谁抓，他可以从三堆中任意一堆、二堆或三堆中抓任意多个，从多堆中抓必须要求抓的数相等。不能不抓。
最后准有一个人没有可抓的就算输。

问题是怎样保证你不输？规律是什么？
问题如果只限从一堆抓，已经解决。

例如n1=7，n2=8，n3=10 （7  8  10）
第一人从第三堆抓5个，（7  8  5）第二人从第一、第二堆各抓6个。（1 2  5）
第一人从第三堆抓5个，（1  2  0）第二人怎么抓都抓不完，比如从第二堆中抓1个，（1  1  0  ），那么第一人从第一第二堆各抓一个完。第二人输。（0  0  0 ）

[ 本帖最后由 hubo5563 于 2010-8-16 22:30 编辑 ]

作者: shzxlin 时间: 2010-8-16 22:25:00

看得不是很懂。。能详细一点么

作者: kattokid 时间: 2010-8-16 22:36:10

看懂了，挺有意思的。先占楼了

作者: 夜雨听风 时间: 2010-8-16 22:39:52

终于看懂了为了不输的原因是不能让剩下的的石子数目相同如果剩下2 堆这2堆数目不能一样，如果剩下一堆必输，剩下3堆的话不要让数目一样

作者: kattokid 时间: 2010-8-17 00:41:52

很明显，剩三堆不是明智之举，最好的办法就是“降阶”，将三堆降到两堆，最后结果必将降到最简，一堆为1，一堆为2，对方怎么选都是输…具体思路再想想

作者: hubo5563 时间: 2010-8-17 09:14:05 标题: 回复 5# 的帖子

对于（7  8  10）来说，你抓走哪堆我都有对付的办法：
如果你抓走第一堆（0  8 10），我从第二、第三堆各抓5个（0  3  5）你必输。
如果你抓走第二堆（7 0  10），我从第三堆抓6个  （7 0 4）你必输。
如果你抓走第三堆（7  8 0），我从第一堆、第二堆各抓6个  （1  2  0）你也必输。
所以不能一次就变成两堆，降阶法不灵。

[ 本帖最后由 hubo5563 于 2010-8-17 09:21 编辑 ]

作者: ursace 时间: 2010-8-17 09:40:32

3个人啊，原来研究过2个人只抓1堆的任意个，各是3、5、7，先抓必胜

作者: 相思常青 时间: 2010-8-18 17:17:41

原帖由 hubo5563 于 2010-8-17 09:14 发表
对于（7  8  10）来说，你抓走哪堆我都有对付的办法：
如果你抓走第一堆（0  8 10），我从第二、第三堆各抓5个（0  3  5）你必输。
如果你抓走第二堆（7 0  10），我从第三堆抓6个  （7 0 4）你必输。
...

所以说，当三堆数目都不相等时，不能全部抓一堆，否则必输。
——————
我数学不咋好，但还是可以得出个结论

作者: hubo5563 时间: 2010-8-18 19:56:53 标题: 回复 8# 的帖子

“当三堆数目都不相等时，不能全部抓一堆，否则必输。”这个结论也不对。
例如：
对于（7 8 10），如果你从第二堆中抓4个，（7 4 10），我就抓走第三堆，（7 4 0），你必输。

作者: kangliqiang 时间: 2010-8-18 21:01:46

都是高手。。。我看晕了。

作者: hubo5563 时间: 2010-8-18 21:05:55 标题: 回复 10# 的帖子

（0 8 10），（0 3 5）.，（0 3 4），第2堆、第三堆各抓2个，（0 1 2）
（7 0 10），（7 0 4），（3 0 4），第一堆、第三堆各抓2个，（1 0 2）

[ 本帖最后由 hubo5563 于 2010-8-18 21:08 编辑 ]

作者: phileas 时间: 2010-8-18 22:57:35

如果只有两堆，其解是互补数列{[na]}, {[nb]}，其中a=二分之根号五加一，b=二分之根号五加三。

猜想：对于三堆，其解同样是互补数列。

作者: hubo5563 时间: 2010-8-19 08:26:09 标题: 回复 12# 的帖子

对于三堆还找不到这样的公式。
这就是难点。

两堆的奇异局势也是三堆的奇异局势，算法是你给出的公式。

（0 0 0），（0 1 2），（1 1 4），（0 3 5），（2 2 6），（1 3 3），（1 5 6），（2 3 8），（2 4 10），（3 4 4），（5 5 7），等都是奇异局势。

一直找不到公式，但可以用计算机编程计算出任意多组这样的奇异局势。

对于奇异局势，除了（0 0 0）是最终状态，其他任何一个奇异局势，经过任何一个合法的抓法必然变为非奇异局势。
任何一个非奇异局势，存在一个合法的正确抓法变为奇异局势。

如果两个对局的人都会，碰到奇异局势的人必输。

[ 本帖最后由 hubo5563 于 2010-8-20 16:37 编辑 ]

作者: phileas 时间: 2010-8-19 13:21:07

对，可以从(0, an, bn)出发，得到递归定义的集合。这个递归如果数学上不能解决，那也是常见的事情。

作者: 相思常青 时间: 2010-8-19 16:02:46

原帖由 hubo5563 于 2010-8-18 19:56 发表
“当三堆数目都不相等时，不能全部抓一堆，否则必输。”这个结论也不对。
例如：
对于（7 8 10），如果你从第二堆中抓4个，（7 4 10），我就抓走第三堆，（7 4 0），你必输。

看来我还是再回去学几年数学吧。。。。。。。。

作者: kattokid 时间: 2010-8-20 12:11:25

这题其实最后两组所剩的数据必须为n和2n-1，n>2，如（3，5），（4，7），（5，9），（6，11）…如果你取完最后两组这种数据那就赢定了，只是我还没想出该如何才能得到这种结果

作者: hubo5563 时间: 2010-8-20 14:51:08 标题: 回复 16# 的帖子

不是这样的。（3,5）、（4,7）是奇异局势，而（5,9）、（6,11）不是奇异局势。
对于（5,9），我从第二堆抓6个，就变成（5,3）你必输。
对于（6,11），我从第二堆抓1，就变成（6,10），（6,10）是奇异局势，所以你也必输。
对于两堆，奇异局势如下：
（0,0）、（1,2）、（3,5）、（4,7）、（6,10）、（8,13）、（9,15）、（11,18）、（12,20）........

第n组奇异局势为（an，bn），an=n×[(1+根号5)÷2]取整数部分,bn=n×[(3+根号5)÷2]取整数部分。

例如：第6组奇异局势
按公式计算：an=6×1.618034=9.708204取整为9
                  bn=6×2.618034=15.708204取整为15
                  所以第6组奇异局势为（9,15）。
                  注意，取整不要四舍五入。

[ 本帖最后由 hubo5563 于 2010-8-20 15:20 编辑 ]

作者: kattokid 时间: 2010-8-20 15:20:17 标题: 回复17楼

原来奇异局势是这样，小弟孤陋寡闻了，受教了

作者: hubo5563 时间: 2010-8-20 15:29:04

对于三堆的奇异局势，我也构造了一个奇异局势表。有这个表，会用这个表，就能百战百胜。
奇异局势表.jpg

对于给定局势，（a，b，c）假定a<=b<=c。
首先查看a列b行那个数假定为d；
如果d=c，那么这就是一个奇异局势，如果对手会玩这个游戏，你必输。否则，你随便从任一堆中取，等待对方出错。
如果d<c，那么从c中取c-d个，变为（a,b,c-(c-d))=(a,b,d)为奇异局势，对方必输。
如果d>c，那么分如下几种情况：
   首先从d往上找，如果发现有c，假定c在b1行，那么从第二堆中取走b-b1个，变为（a，b-(b-b1),c)=(a,b1,c)这是个奇异局势。对方必输。
   如果从d往上找找不到c，再从d往左找，如果发现c在a1列，那么从第一堆中取走a-a1个，变为（a-(a-a1)，b，c)=(a1,b,c)这是个奇异局势。对方必输。
   如果还没找到c，再从d往左上方沿对角线45度方向找，如果发现c在a1列b1行，此时a-a1和b-b1相等，那么从第一堆中取走a-a1个，从第二堆中取走b-b1个变为（a-(a-a1)，b-(b-b1)，c)=(a1,b1,c)这是个奇异局势。对方必输。
   如果还找不到c，变换查找方式，从d上面第一格开始，往上找，每次比较前，将c减去1，直到第一行。如果第i次发现相等了，那么（a，b-i，c-i）为表中的奇异局势。就从第二堆和第三堆各取i个，变为奇异局势，对方必输。
   如果找不到相等的，从d左面前一格开始，往左找，每次比较前，将c减去1，直到第一列。如果第i次发现相等了，那么（a-i，b，c-i）为表中的奇异局势。就从第一堆和第三堆各取i个，变为奇异局势，对方必输。
   如果找不到相等的，从d左上方第一格开始，沿着45度方向往左上找，每次比较前，将c减去1，直到第一列或第一行。如果第i次发现相等了，那么（a-i，b-，c-i）为表中的奇异局势。就从第一堆和第二堆以及第三堆各取i个，变为奇异局势，对方必输。
   奇异局势表的构造方法保证通过以上办法能够找到正确取法。

   例如：（7,8,10）
               从7行8列看是24,24比10大。24上方、左方、左上方都没有10,24上方第一个不是10-1，第二个是10-2=8；因此正确抓法是从第一堆和第三堆各抓2个，变为（5,8,8）是奇异局势。
例如：（4,6,17）
            从4行6列看是15,17比15大，从第三堆取走2个，变为（4,6,15）是奇异局势。
   例如：（4,6,9）
            从4行6列看是15,15比9大，从15往上看，第一个是9，因此从第一堆中取走1，变为（3,6,9）为奇异局势。
   例如：（4,6,10）
            从4行6列看是15,15比10大，从15往左上角查时发现，15左上角第2个是10，所以从第一、第二堆各取2个，变为（2,4,10）为奇异局势。
例如：（4,6,6）
            从4行6列看是15,15比6大，从15往左上递减检查时发现，第一个查5，第二个查4，第三个查3，正好是3。因此从三堆中各取走3个变为（1,3,3）为奇异局势。

[ 本帖最后由 hubo5563 于 2010-8-20 17:16 编辑 ]

附件: 奇异局势表.jpg (2010-8-20 15:33:36, 148.51 KB) / 下载次数 51
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTA5MjY4fDI3YmUzOGY3fDE3MzA0MzIzNjN8MHww

作者: yzsjw0 时间: 2010-8-20 16:09:45

三个经典数学博弈
（一）巴什博奕（Bash Game）：只有一堆n个物品，两个人轮流从这堆物品中取物，规
定每次至少取一个，最多取m个。最后取光者得胜。

显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，
后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果
n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走
k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的
取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。
这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十
个，谁能报到100者胜。
（二）威佐夫博奕（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同
时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，...,n)表示
两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们
称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，
10）、（8，13）、（9，15）、（11，18）、（12，20）。

可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k，奇异局势有
如下三条性质：

1。任何自然数都包含在一个且仅有一个奇异局势中。
由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而 bk= ak + k > ak
-1 + k-1 = bk-1 > ak-1 。所以性质1。成立。
2。任意操作都可将奇异局势变为非奇异局势。
事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其
他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由
于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。
3。采用适当的方法，可以将非奇异局势变为奇异局势。

假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了
奇异局势（0，0）；如果a = ak ，b > bk，那么，取走b  - bk个物体，即变为奇异局
势；如果 a = ak ，  b < bk ,则同时从两堆中拿走 ak - ab - ak个物体,变为奇异局
势（ ab - ak , ab - ak+ b - ak）；如果a > ak ，b= ak + k,则从第一堆中拿走多余
的数量a - ak 即可；如果a < ak ，b= ak + k,分两种情况，第一种，a=aj （j < k）
,从第二堆里面拿走 b - bj 即可；第二种，a=bj （j < k）,从第二堆里面拿走 b - a
j 即可。

从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜
；反之，则后拿者取胜。

那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：

ak =[k（1+√5）/2]，bk= ak + k  （k=0，1，2，...,n 方括号表示取整函数)

奇妙的是其中出现了黄金分割数（1+√5）/2 = 1。618...,因此,由ak，bk组成的矩形近
似为黄金矩形，由于2/（1+√5）=（√5-1）/2，可以先求出j=[a（√5-1）/2]，若a=[
j（1+√5）/2]，那么a = aj，bj = aj + j，若不等于，那么a = aj+1，bj+1 = aj+1
+ j + 1，若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异
局势。

（三）尼姆博奕（Nimm Game）：有三堆各若干个物品，两个人轮流从某一堆取任意多的
物品，规定每次至少取一个，多者不限，最后取光者得胜。

这种情况最有意思，它与二进制有密切关系，我们用（a，b，c）表示某种局势，首
先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是
（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一
下，（1，2，3）也是奇异局势，无论对手如何拿，接下来都可以变为（0，n，n）的情
形。

计算机算法里面有一种叫做按位模2加，也叫做异或的运算，我们用符号（+）表示
这种运算。这种运算和一般加法不同的一点是1+1=0。先看（1，2，3）的按位模2加的结
果：

1 =二进制01
2 =二进制10
3 =二进制11 （+）
———————
0 =二进制00 （注意不进位）

对于奇异局势（0，n，n）也一样，结果也是0。

任何奇异局势（a，b，c）都有a（+）b（+）c =0。

如果我们面对的是一个非奇异局势（a，b，c），要如何变为奇异局势呢？假设 a < b
< c,我们只要将 c 变为 a（+）b,即可,因为有如下的运算结果: a（+）b（+）(a（+）
b)=(a（+）a)（+）(b（+）b)=0（+）0=0。要将c 变为a（+）b，只要从 c中减去 c-（
a（+）b）即可。

例1。（14，21，39），14（+）21=27，39-27=12，所以从39中拿走12个物体即可达
到奇异局势（14，21，27）。

例2。（55，81，121），55（+）81=102，121-102=19，所以从121中拿走19个物品
就形成了奇异局势（55，81，102）。

例3。（29，45，58），29（+）45=48，58-48=10，从58中拿走10个，变为（29，4
5，48）。

作者: hubo5563 时间: 2010-8-20 16:23:32 标题: 回复 20# 的帖子

这个游戏是威佐夫博奕和尼姆博奕的推广，比这三个经典游戏难。
如果三堆变为两堆，就是威佐夫博奕，所以威佐夫博奕是这个游戏的特例。
如果只限从一堆中取，就是尼姆博奕。由于规则不同，所以尼姆博奕的奇异局势与本游戏不同。奇异局势没有异或和为0的性质。

[ 本帖最后由 hubo5563 于 2010-8-20 16:55 编辑 ]

作者: takijianshao 时间: 2010-8-21 01:32:12

怎么看到9L的时候都糊涂了。。。。。。

作者: Cielo 时间: 2010-8-23 17:59:05

来学习一下！

发现楼主也是发帖很少的前辈啊

作者: Atato 时间: 2010-8-25 13:58:52

有意思.实践一下才行.

作者: ggglgq 时间: 2011-7-18 16:39:41

　　
　　

今天才发现楼主的相关软件，支持一下！

摘珠子.rar http://bbs.mf8-china.com/attachment.php?aid=151545

http://bbs.mf8-china.com/viewthread.php?tid=79719

　　
　　


　　
　　
　　

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)