描述
有一堆n个棋子,两个玩家轮流从堆中拿走至少一个至多m个棋子,
每次拿的棋子数都可以不同,如果每个玩家都做出了最佳选择,哪个玩家能够顺利拿走最后一个棋子?
解析
这种游戏的原型实例是拈游戏中的单堆棋子版本。现在假设游戏已经进行了一会,双方都能做出最佳选择,现在轮到你
情况:
1. 如果n=0,也就是你已经没法走了,输
2. 如果n=1~m,你可以拿走剩下全部棋子,下一步对方的情况是1,赢
3. 如果n=m+1,都会把对方推向情况2,输
4. 如果n=m+2 ~ 2m+1(即m+1+m),拿走(1~m)个,将对方推向情况3,赢
5. 如果n=2(m+1)=2m+2,拿走任意个,将对方推向情况4,输
结果
- 当n%(m+1)==0,结局必定为输
- 当n%(m+1)!=0,获胜
获胜的策略是取走n%(m+1)个棋子。
实例
假设n=9,m=3。己方先手,按照上面得到的结论推导n%(m+1)!=0,所以己方获胜。
- 9%(3+1)=1,取走1个
- 假设对方拿走3个(为方便)
- 5%4=1,取走1个
- 这次取走1个(随意)
- 3%4=3,全部取走,获胜
总结
所以根据初始n和m算出可以获胜,只要按照确定的公式取走棋子,无论对方如何取都能确保获胜。
拓展
对于一般性的拈游戏,即有多堆棋子,有一种令人称奇的解法:
基于队中棋子的二进制表示,b1/b2/b3/b4.....为各堆中棋子个数的二进制表示。当且仅当所有二进制异或和中包含至少一个1时,该实例为胜局,当且仅当所有二进制异或和中不包含1时,该实例为输局。(异或和也可以看作没有进位的加法)
如n1=4,n2=5,n3=6
要使对方输,就要使异或和所有位数都为0,这里无法实现。