钟七珍 发表于 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/viewthread.php?tid=81983&extra=page%3D1
页: [1]
查看完整版本: 一道难度较大的博弈题