魔方吧·中文魔方俱乐部

标题: 23个棋子围成一个圆圈，每次最多拿三个 [打印本页]

作者: 钟七珍 时间: 2012-6-30 00:34:17 标题: 23个棋子围成一个圆圈，每次最多拿三个

本帖最后由钟七珍于 2012-6-30 02:21 编辑

　　有23个棋子围成一个圆，甲乙二人比赛，两人在圆圈上轮流拿棋子，每次只能拿1个、或者连续的2个、或者连续3个棋子（最多拿3个，最少拿1个），不能拿不相连的棋子（若两颗棋子之间夹有的棋子被拿开了，仍然视为不连续）：轮到一人拿棋子时，可以从任一个地方拿。胜负规则是：圆圈上的棋子拿完之后，谁拿的总数是单数者胜，拿双数者负。若甲先拿，谁会赢？

作者: 洛阳狼王 时间: 2012-6-30 00:53:45

甲会赢。

作者: Fenz 时间: 2012-6-30 12:00:49

这种游戏都是后手胜。
我的方法是：
前面四回合如果甲拿1，乙就在他旁边拿3；甲拿2，乙也拿2；甲拿3，乙就拿1。保证每回合都被拿掉相连的4个子。
四回合下来还剩7颗，接下来情况比较多，但是乙都可以根据甲那多少决定自己那多少，保证胜利

作者: 西北天狼 时间: 2012-7-4 09:00:56

Fenz 发表于 2012-6-30 12:00
这种游戏都是后手胜。
我的方法是：
前面四回合如果甲拿1，乙就在他旁边拿3；甲拿2，乙也拿2；甲拿3，乙就 ...

总：23  甲：0  乙：0
总：19  甲：1  乙：3
总：14+1  甲：1+1  乙：3+3
总：8+2+1  甲：1+1+1  乙：3+3+3
总：2+2+2+1  甲：1+1+1+1  乙：3+3+3+3
总：2+2+1+1  甲：1+1+1+1+1  乙：3+3+3+3+？
甲赢！这种策略不行。

作者: Fenz 时间: 2012-7-9 21:42:36

西北天狼发表于 2012-7-4 09:00
总：23  甲：0  乙：0
总：19  甲：1  乙：3
总：14+1  甲：1+1  乙：3+3

总：23  甲：0  乙：0
总：19  甲：1  乙：3
总：14+1  甲：1+1  乙：3+3
总：8+2+1  甲：1+1+1  乙：3+3+3
总：2+2+2+1  甲：1+1+1+1  乙：3+3+3+3
总：2+2+1  甲：1+1+1+1+1  乙：3+3+3+3+1
总：1+1+1  甲：1+1+1+1+1+1  乙：3+3+3+3+1+1
总：1  甲：1+1+1+1+1+1+1  乙：3+3+3+3+1+1+1
总：0  甲：1+1+1+1+1+1+1+1  乙：3+3+3+3+1+1+1
乙赢

总：23  甲：0  乙：0
总：19  甲：1  乙：3
总：14+1  甲：1+1  乙：3+3
总：8+2+1  甲：1+1+1  乙：3+3+3
总：2+2+2+1  甲：1+1+1+1  乙：3+3+3+3
总：2+2+1  甲：1+1+1+1+1  乙：3+3+3+3+1
总：2+1  甲：1+1+1+1+1+1  乙：3+3+3+3+1+1
总：1  甲：1+1+1+1+1+1+1  乙：3+3+3+3+1+1+1
总：0  甲：1+1+1+1+1+1+1+1  乙：3+3+3+3+1+1+1
乙赢

总：23  甲：0  乙：0
总：19  甲：1  乙：3
总：14+1  甲：1+1  乙：3+3
总：8+2+1  甲：1+1+1  乙：3+3+3
总：2+2+2+1  甲：1+1+1+1  乙：3+3+3+3
总：2+2+1  甲：1+1+1+1+1  乙：3+3+3+3+1
总：1  甲：1+1+1+1+1+2  乙：3+3+3+3+1+2
总：0  甲：1+1+1+1+1+2+1  乙：3+3+3+3+1+2
乙赢

作者: flwb 时间: 2012-7-10 21:51:57

Fenz 发表于 2012-6-30 12:00
这种游戏都是后手胜。
我的方法是：
前面四回合如果甲拿1，乙就在他旁边拿3；甲拿2，乙也拿2；甲拿3，乙就 ...

甲会那么老实?总在一个地方拿?乙若跟着他旁边拿,下次就到对面拿,把链条打断为若干段,还是挺复杂的!

作者: lulijie 时间: 2012-7-11 22:27:55

本帖最后由 lulijie 于 2012-7-11 22:31 编辑

答案.rar (5.67 KB, 下载次数: 9)

设棋子的总数为n，若n围成圈，那么g(n)表示其胜负值，若n不围成圈，那么f(n)表示其胜负值，若n不连续，那么用逗号隔开，如f(1,1,3)
f()=0 ,表示先手方的奇偶由后行方决定；那么无论奇胜还是偶胜，都是先手方败。
f()=1 ,表示先手方可确保拿到奇数，若后手方不让，定拿不到偶数；若奇胜，则先行方胜，偶胜则先行方败。
f()=2 ,表示先手方可确保拿到偶数，若后手方不让，定拿不到奇数；若奇胜，则先行方败，偶胜则先行方胜。
f()=3,表示先手方可自行决定拿奇数还是拿偶数；那么无论奇胜还是偶胜，都是先手方必胜。
-------------------------------------------------------------------------------------------------------------------
楼主所求的等于g(23), 那么取决于f(20),f(21),f(22)
因为f(20)=3,f(21)=3,f(22)=2
所以先行方必取1个棋子，使得棋子成连续的22个棋子的局面，后行方必得偶数，所以先行方必得奇数而获胜。
以下是一些f()值和g()值，详细的f()值见附件。
f(1)=1
f(2)=3
f(3)=3
f(4)=3
f(5)=3
f(6)=3
f(7)=3
f(8)=3
f(9)=3
f(10)=3
f(11)=3
f(12)=1
f(13)=2
f(14)=3
f(15)=3
f(16)=2
f(17)=1
f(18)=3
f(19)=3
f(20)=3
f(21)=3
f(22)=2

g(1)=1
g(2)=3
g(3)=3
g(4)=1
g(5)=0
g(6)=0
g(7)=0
g(8)=0
g(9)=0
g(10)=0
g(11)=0
g(12)=0
g(13)=2
g(14)=3
g(15)=3
g(16)=2
g(17)=1
g(18)=3
g(19)=3
g(20)=1
g(21)=0
g(22)=0
g(23)=1

附件: 答案.rar (2012-7-11 22:30:06, 5.67 KB) / 下载次数 9
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTg2MDA3fDU1NDE0OGNlfDE3MTUxNTIwOTd8MHww

作者: 钟七珍 时间: 2012-7-15 11:46:16

lulijie 发表于 2012-7-11 22:27
设棋子的总数为n，若n围成圈，那么g(n)表示其胜负值，若n不围成圈，那么f(n)表示其胜负值，若n不连续， ...

又是老师编程得出此题结果！谢谢！下载后再慢慢学习消化。

作者: 钟七珍 时间: 2012-7-15 23:40:51

lulijie 发表于 2012-7-11 22:27
设棋子的总数为n，若n围成圈，那么g(n)表示其胜负值，若n不围成圈，那么f(n)表示其胜负值，若n不连续， ...

我给你发了一条消息。

作者: lulijie 时间: 2012-7-16 20:16:24

本帖最后由 lulijie 于 2012-7-16 20:17 编辑

钟七珍发表于 2012-7-15 23:40
我给你发了一条消息。

谢谢楼主的提醒，原计算程序确实有误，穷举局面的时候有遗漏。
下面是改正后计算出的结果，先手败。
f(1)=1
f(2)=3
f(3)=3
f(4)=3
f(5)=3
f(6)=3
f(7)=3
f(8)=3
f(9)=3
f(10)=3
f(11)=3
f(12)=3
f(13)=3
f(14)=3
f(15)=3
f(16)=3
f(17)=3
f(18)=3
f(19)=3
f(20)=3
f(21)=3
f(22)=3

g(1)=1
g(2)=3
g(3)=3
g(4)=1
g(5)=...=g(23)=0

MyDB.rar (33.12 KB, 下载次数: 6)

附件: MyDB.rar (2012-7-16 20:16:11, 33.12 KB) / 下载次数 6
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTg2MjQ3fDVhMDEzYzU3fDE3MTUxNTIwOTd8MHww

作者: lulijie 时间: 2012-7-16 20:33:05

下面总结一下，把先手必奇、必偶局面提取出来，剩下的都是先手可奇可偶(必胜)局面。

先手必奇、必偶局面.rar (4.65 KB, 下载次数: 6)

附件: 先手必奇、必偶局面.rar (2012-7-16 20:32:36, 4.65 KB) / 下载次数 6
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MTg2MjQ4fDk2NGJmNjBhfDE3MTUxNTIwOTd8MHww

作者: lulijie 时间: 2012-7-16 21:53:11

23-->>
   22 -->>11,10(必奇)
   21-->> 10,10（必偶）
   20-->> 9,8（必奇）
环23局面：先行方取奇数(1个或3个)，后行方取后形成必奇局面，先行方取偶(2个)，后行方取后形成必偶局面。

作者: lulijie 时间: 2012-7-16 22:27:51

本帖最后由 lulijie 于 2012-7-16 22:52 编辑

f(n,n+1)=f(n+1,n+1)，后手方必能做到让先手方拿到n+1个棋子，(先手方拿什么，后手方按照对称来拿) 对于少一个棋子的堆，后手方就想象其中有一个假想的棋子存在即可。
所以对于任何4n+1，先手方无论形成任何局面，后手方都有对策：
      4n-->>2n-1,2n-1(必奇)
      4n-1-->>2n-2,2n-2（必偶）
   4n-2-->> 2n-1,2n-2（必奇）
  而对于任何4n+3，先手方无论形成任何局面，后手方也有对策：
      4n+2-->>2n+1,2n(必奇)
      4n+1-->>2n,2n（必偶）
   4n-->> 2n-1,2n-1（必奇）
---------------------------------------------------------------
所以对于环形的奇数个棋子，先行方都必败。偶数个棋子胜也是同样道理，后手方都可以形成对称局面(偶数堆棋子，可以存在一个假想棋子)而获胜。

作者: Fenz 时间: 2012-7-17 11:44:39

flwb 发表于 2012-7-10 21:51
甲会那么老实?总在一个地方拿?乙若跟着他旁边拿,下次就到对面拿,把链条打断为若干段,还是挺复杂的!

我这里已经包含你所说的那种拿法的所有情况了呀

作者: 钟七珍 时间: 2012-7-18 09:42:42

谢谢老师！

作者: 钟七珍 时间: 2012-7-18 09:46:38

lulijie 发表于 2012-7-16 20:16
谢谢楼主的提醒，原计算程序确实有误，穷举局面的时候有遗漏。
下面是改正后计算出的结果，先手败。
...

谢谢老师！N≥5 时，都是后手胜，这个结果没想到。

作者: 钟七珍 时间: 2012-7-22 14:28:04

lulijie 发表于 2012-7-16 20:16
谢谢楼主的提醒，原计算程序确实有误，穷举局面的时候有遗漏。
下面是改正后计算出的结果，先手败。
...

谢谢lulijie 老师！

作者: 双子流星 时间: 2015-5-19 23:13:44

看这篇看了十几分钟，没看出什么

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