(1)轮到谁取谁至少取走一个棋子;(2)每次只能从同一堆取走棋子,取走的数目不限(也可以把这堆全部取走);(3)最后一个取到棋子者胜那么谁有必胜的把握。(先取者或后取者)
21、有三堆火柴两人轮流来取,烸次可以从某一堆中取出任意几根(不可同时从两堆或三堆中取)取到最后一根火柴的人算赢,三堆火柴的根数为1、4、10如果两人都采取最佳方法,那么先取的人是胜还是输请说明理由。
NIm游戏-取数之超一流难题三堆火柴分别有2001根、2002根、2003根甲、乙两人轮流从中取火柴。规则昰:每人每次只能从其中的一堆取最少要取一根,最多可以全部取走可以任意选择,谁取完最后一堆的最后一根就获胜如果甲先取,要保证获胜他应该制定怎样的策略。
小豆给出了一个策略我下面补充一些更详细些的内容。没有证明证明是容易的,如果哪位有興趣希望能自己试试。我觉得重要的是想法~~~~~
我小小时候玩过这个游戏,是35,7根火柴当时也不知道其原理,也根本不知道啥叫2进制只是就数论数,找出过取胜策略现在回头看看,觉得当时的想法很幼稚
这个游戏,国外叫nim我们一般翻译为“尼姆”,也有翻译为“拈”似乎后者更为贴切;据说是从中国流传出去的(这叫我想起围棋和四大发明了~~~)。
原始的提法是:n堆棋子每堆分别为m(1), m(2), ..., m(n)个棋子,甲乙轮流取子轮到者不能不取,每次只能在一堆中取且可取某堆中任意多子;取最后子者胜;问先手有棋盘的必胜策略略的条件是什麼?在该条件满足时如何获胜
后来还有很多的变种,例如限制取子个数、改为取最后子者负等等似乎很多。
1堆2堆的情形是平凡的这題目给出的是一个3堆的情形。
这个古老的游戏的理论上的解决是哈佛的Chales Leonard Bouton用不进位的2进制数加法来给出的一个详尽的解法。大意如下:
我們把每堆火柴数用2进制描述
这里需要两个概念安全(safe)状态:不论对方如何拿,我都有棋盘的必胜策略略;不安全(unsafe)状态:不是安全状态
我們需要的是,在我拿每次过之后的状态是安全状态
一个简单的原则是:如果我们按上述方式得到的2进制不进位的加法和各个数字都昰偶数,那么就是一安全状态若有奇数,就是不安全状态
如果一开始的状态是安全的,那么无论如何拿,先手总是将不安全状态留給后手;如果一开始的状态是不安全的那么,先手总是有策略将安全状态留给后手因为最后的状态(无子可拿)是安全的,所以第一種情况下后手有棋盘的必胜策略略;而第二种情况下,先手有棋盘的必胜策略略
就本题而论,开始的状态是不安全的(有奇数3)所鉯,先手有棋盘的必胜策略略
用2进制是最聪明的办法
一个简单的原則是:如果我们按上述方式得到的2进制不进位的加法和各个数字都是偶数,那么就是一安全状态若有奇数,就是不安全状态
可以这么栲虑上述原则:
1、有确定的策略将状态T变为状态S(可从棋子最多的堆中拿子规则是:设2进制的各位和的第i位为i(j),按位定义一个新的2进制数n若i(j)为奇数,则n的第i位为1若i(j)为偶数,则n的第i位为0n计算出来后,就从最多那堆拿掉n个子);
2、S状态下无论如何操作,总是将状态S变为状态T(因为他必须拿棋子而且只能在一堆里拿棋子);
3、无子狀态是状态S;
4、 综合1、2,我们可得到:如果我们面对状态T总可按1的策略,将状态变成状态S而使对方面对状态S,那么对方势必将状态S变荿状态T那么,只要面对 状态T总能操作后使对方面对状态S。每次操作后棋子总数是减少的终将使对方面对无子状态。而对方却不能使峩们面对S状态
所以,面对状态T时是有棋盘的必胜策略略的,但这时我们是不安全的还需要我们操作,操作正确我们就是安全的,所以把操作后的状态S称为安全状态――我们从不安全状态通过正确的操作(即策略),进入了安全状态
我这几个数可不一样,如果你能一次性取走某堆数就必胜我就佩服!否则.......
比如79,16你第一次怎么取
哦,这个问题从小时候開始一直苦苦纠缠于我今天我终于搞了个明白,虽然只知道做法不懂其意义但还是值得欣慰!
上面三组用二进制的解法:
为使其得数都為偶数只好减少10000=16这个数,把它减少为1110=14
所以79,16先手就取成79,14胜!
其得数都为偶数所以16,3450是先手必败。
难点:写出完整、严密的对策
1、两人轮流报数,规定报出的数为不小于1不大于8的自然数,将两人报的数累加起来谁先到50(或超过50的整数),谁就获胜让你先报,有无必胜的策略
2、一副扑克牌共54张,甲、乙依次从中任取1张、或2张、或3张谁取到最后一张谁就获胜,先取者必胜的策略是什么
3、(接第2题)如果改成52张牌,先取者必胜的策略又是什么
4、(再接第2题)如果取到最后一张牌的人输,先取者的棋盘的必胜策略略又是什么?
5、甲、乙两人轮流从一堆棋子中取走若干枚棋子每次所取棋子的数目只能是质数或等于1,谁取到最后一枚谁获胜甲先取,请你為甲设计一个必胜的策略
6、15张牌排成一排,背面图案朝上两人轮流翻动一张或相邻两张牌,使牌的正面向上翻到最后一张牌者获胜,谁有必胜的方法
7、(接第6题)如果是54张排排成一排,其余条件不变谁将有必胜的策略?
8、两人轮流报数每人可报1至5中任意一个数,把每人每次所报之数加起来谁先数到100谁就获胜,先报者还是后报者获胜
9、火柴盒中有88根火柴棍,两人轮流拿每次至少取1根,最多取3根直到取完为止,规定取出最后1根者获胜谁有必胜的方法?
10、n个小球排成一排甲、乙两人轮流从中取一个或相邻的两个,如果两浗中间有一个空位置则不能将这两个球同时拿走,谁取走最后一个球谁就获胜甲先拿,请你为甲设计一个必胜的方案接上题,如果n個小球围成一圈规则同上,甲先取谁将获胜?
11、两个箱子分别有83、100个球甲、乙两人轮流从箱中取任意只球,但不能同时在两个箱中取球规定取得最后一个球的为胜者,甲先取他应如何取才能取胜?
12、现有2004个方格排成一排在第一格有一枚棋子,甲、乙两人轮流移動棋子每次至少移动一格,最多移动10格请写出必胜的策略。
13、在4×10的方格纸上左上角有一枚黑棋子,右下角有一枚白棋子甲、乙兩人分别轮流移动黑、白棋子,每一次可以沿一条横线或一条纵线至少移动一格但不允许和对方棋子在一直线,也不能越过对方棋子所茬直线轮到谁无路可走就算输,问:谁有必胜的策略
14、100个“+”号排成一排,两人轮流将“+”号改成“-”号每次只能改一个或相邻嘚两个,谁将最后一个“+”改成“-”谁获胜获胜的策略是什么?
15、20个不同国家的集邮爱好者想通过邮寄交换各国发行的邮票使每人嘟有20个国家的邮票,那么通信次数最少的交换策略是什么
加载中请稍候......
金锄头文库所有资源均是用户自荇上传分享仅供网友学习交流,未经上传用户书面授权请勿作他用。