魔方吧·中文魔方俱乐部

标题: 看你的策略是什么？你能赢吗？ [打印本页]

作者: Get_FBlood 时间: 2009-10-7 12:57:34 标题: 看你的策略是什么？你能赢吗？

A，B从一堆玻璃球（共100个）里向外拿球，规则如下：
(1)A先拿，然后一人一次交替着拿；
（2）每次只能拿1个或2个或4个；
（3）谁拿最后一个球，谁就是最后的失败者；
问A，B谁将是失败者？写出你的判断步骤。

作者: 123wyx 时间: 2009-10-7 13:17:02

3N+1先拿必败

作者: danil0816 时间: 2009-10-7 13:19:02

A是失败者。只要每一次A拿完，B都去凑5的倍数，比如说A拿了2，那么B拿3，然后A拿1，B拿4，确保每一轮拿完后都是5的倍数，B稳赢，如果是101的话。。。。。。。。那就是A赢了。

作者: wwd_meng 时间: 2009-10-7 13:19:45

我猜是A赢
只要Ａ一直保持被拿走球是４的倍数就肯定赢

作者: superacid 时间: 2009-10-7 13:25:41

原帖由 wwd_meng 于 2009-10-7 13:19 发表
我猜是A赢
只要Ａ一直保持被拿走球是４的倍数就肯定赢

如何保持？

作者: superacid 时间: 2009-10-7 13:27:30

原帖由 danil0816 于 2009-10-7 13:19 发表
A是失败者。只要每一次A拿完，B都去凑5的倍数，比如说A拿了2，那么B拿3，然后A拿1，B拿4，确保每一轮拿完后都是5的倍数，B稳赢，如果是101的话。。。。。。。。那就是A赢了。

不能拿3个...

作者: danil0816 时间: 2009-10-7 13:28:27

4l可以想一想，80起（既是我说的5的倍数，又是4的倍数）。先照你说的1 3 1 3 1 3 这时是92个，还有8个然而只能比96小，如果报道96，那么游戏结束。所以只能报3，赢了。由于a先报，按你说的，也就是a报的80。但是最后是B赢的。所以4l误解

作者: superacid 时间: 2009-10-7 13:28:56

这题目没有想象中的那么简单

作者: danil0816 时间: 2009-10-7 13:29:32

:Q 居然不能拿3个。。。。。。。。。。。。。。。。。我晕。那。。。。。。。。。。。。

作者: 小杨杨 时间: 2009-10-7 14:41:58

不管结果怎么样，A,B两人拿的都是50个球吧，那把100个球想象成两堆各50个， AB只管抽自己面前的那堆，

不管A怎么抽，B要想不输肯定要往快了抽吧，那就假设他每次都是4个，但是A看他抽4个肯定也要抽4个，

那么 50处以4余2吧，就是说还剩最后两个各剩2个，显然B will win this game!

作者: wwd_meng 时间: 2009-10-7 15:52:18

原帖由 superacid 于 2009-10-7 13:25 发表

如何保持？

呵呵
计算错误，因为不能拿3个
所以这个问题很麻烦，所以我是解不了了

作者: 铯_猪哥恐鸣 时间: 2009-10-7 15:53:28

1、很容易证明7个以下的情况是：
a[0]=true
a[1]=false
a[2]=true
a[3]=true
a[4]=false
a[5]=true
a[6]=true
a[7]=false
（true表示待拿者胜利。例：a[0]=true，就是说还有0个球的时候下一位取球的胜利，，这是根据规则显然的）

对于7个以上的情况，若A取1则B取2（共取3），A取2则B取4，若A取4则B取2（共取6），总之每轮取完之后结果仍然为3N+1的数字。然后容易发现，a[7]=false,a[4]=false,a[1]=false。所以先取的人必败

作者: lulijie 时间: 2009-10-7 19:26:02

楼上完全正确，A取2时，B可取4，也可取1。
对于这类题目，用倒推的方法基本上都能解出。
－－－－－－－－－－－－－－－－－－－
若把题目推广到几堆球，难度就大了一些。
－－－－－－－－－
n堆球，每堆的球数都是100个，每次只能从一堆中拿球，每次拿球的个数是1、2、4个球，谁拿走最后一个球，算谁输。
那么先行方是赢还是输？
－－－－－－－－－－－－－－

作者: 123wyx 时间: 2009-10-7 20:19:10

原帖由 lulijie 于 2009-10-7 19:26 发表
若把题目推广到几堆球，难度就大了一些。
－－－－－－－－－
n堆球，每堆的球数都是100个，每次只能从一堆中拿球，每次拿球的个数是1、2、4个球，谁拿走最后一个球，算谁输。
那么先行方是赢还是输？

这问题就复杂了，感觉跟二进制有点关系。

作者: phileas 时间: 2009-10-7 21:41:34 标题: 回复 13# 的帖子

首先，计算nim函数，nim(x)= x mod 3。
如果拿到最后一个算赢，那么n堆球就是把上述函数用异或一下即可，结果为0则先行必输，否则先行必胜。
如果拿到最后一个算输，基本上仍然是上述结论。但是需要另外计算一个状态集：
0. 这个状态集是一层一层计算的，每层是0状态和非0状态交替；
1. 这个状态集的起始状态是(1)；
2. 附加一条显然的规则：任何一个状态，加上(1,1)是等价状态。
计算方法大概是这样的：
从非0状态层计算0状态层：把每个非0状态的前驱状态计算一下，如果其值是0，则放入0状态层。
从0状态层计算非0状态层：把每个0状态的前驱状态计算一下，这个状态要满足两个要求：
a. 能得到的0状态必须已经在状态集中。
b. 不能得到状态集中的任何一个非0状态。

对于拿到最后一个算输的问题，结论是：如果某状态在以上状态集中，那么为0则先行必胜，否则先行必输；如果某状态不在以上状态集中，那么为0则先行必输，否则先行必胜。
==========================================================
时间关系，写得不是很清楚，抱歉。

[ 本帖最后由 phileas 于 2009-10-7 21:43 编辑 ]

作者: flwb 时间: 2009-10-8 23:53:18

先手必输,B的原则是:A取1,B取2,A取2 B取1或4,A取4,B取2,保证以3或3的倍数递减至1。

[ 本帖最后由 flwb 于 2009-10-8 23:54 编辑 ]

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