魔方吧·中文魔方俱乐部

标题: 一道难度较大的博弈题 [打印本页]

作者: 钟七珍 时间: 2011-8-17 13:18:15 标题: 一道难度较大的博弈题

　　二人博弈游戏：有27个硬币，每次只能拿走1到4个，拿完后手中的硬币总和为偶数者算赢，问先手拿的是输还是赢？第一步该怎么拿？
　　不失一般性：有2n+1个硬币，两人轮流拿，每次只能拿走1到M(M>=2)个，拿完后手中的硬币总和为偶数者算赢，问先手拿的是输还是赢？第一步该怎么拿？
　　若规定：拿完后手中的硬币总和为奇数者的算赢，又该怎么拿？

作者: 过匆匆 时间: 2011-8-17 13:23:37

后手吧

作者: yq_118 时间: 2011-8-17 20:41:05

假设每次可以取1~4个，
6*n+1个硬币，先手不能保证取偶数个。其它情况先手一定能取到偶数个。
6*n+3，6*n+5个硬币，先手不能保证取奇数个。其它情况先手一定能取到奇数个。

作者: lulijie 时间: 2011-8-18 00:01:15 标题: 标题

3楼正确：若偶数胜，则被6除余数为1的为必奇局面。先行方只要使得剩下的硬币数形成必奇局面即可。
若奇数胜，则先行方使得剩下的硬币数形成6k+5或6k的必偶局面即可。

作者: lulijie 时间: 2011-8-18 00:45:07

对于每次拿1-m个：

那么若m为偶数，那么被m+2除，余1为必奇局面(即先行方必拿到奇数个硬币)，余0和余m-1为必偶局面，余其它为必胜局面（即奇偶由先行方决定）。
若m为奇数，那么被2m+2除，余1和余m+1为必奇局面，余m+2和余0为必偶局面，余其它为必胜局面。

作者: lulijie 时间: 2011-8-18 00:56:27

必奇局面：先行方必拿到奇数个硬币。
必偶局面：先行方必拿到偶数个硬币。
必胜局面：先行方可自行决定拿奇数个硬币还是拿偶数个硬币。
------------------------------------------------------------------------

硬币总数为N，每次取1-m个硬币。
m为偶数：    必奇局面 N mod (m+2)=1
                     必偶局面 N mod (m+2)=0 或 m+1
                     必胜局面剩下的都是
m为奇数：       必奇局面 N mod (2m+2)=1或m+1
                     必偶局面 N mod (2m+2)=0或m+2
                                             必胜局面剩下的都是

作者: 钟七珍 时间: 2011-9-1 23:18:43

楼上朋友正解！顶！
在此题基础上，将一堆增加成三堆，难度加大了。见：http://bbs.mf8-china.com/viewthr ... &extra=page%3D1

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