取石子游戏

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。（PS：不同的两堆石子数目，应该会有不同的结论）

[此贴子已经被作者于2007-7-21 18:36:42编辑过]

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：最好的 游戏 石子

我觉得当石头数量剩下 2和1的时候 先取的一定输，即谁将石头调整为2和1就能取胜

由题目已知的两种方法实际上可以保证一方在任何情况下将石头调整为2：1（不一定是2和1）的状态

所以设石头比例为x:y

情况一 (x!=y, 设x>y)

x = 2*y 先取的输；

否则后取的输。

情况二（x＝y）

先取的赢

好像是这样的！！同意

二楼的不对呀～～

举个例子说明下，比如两堆分别是4，和8

先取者取成4，3。

则不管后取者怎么取，都是必输

所以先取者赢

以下是引用TNTSky在2007-7-22 10:58:00的发言：

二楼的不对呀～～

举个例子说明下，比如两堆分别是4，和8

先取者取成4，3。

则不管后取者怎么取，都是必输

所以先取者赢

我觉得后取的两堆各取2，取成 2，1 （原则就是凑成2：1）这样就还是先取的那个输

1,我觉得如果把两堆的数目分成是 x y

当x=y的时候 先取的胜利 因为同时两堆一起拿 主要是分析x不等于y的时候

当x不等于y, 分析最后胜利的那个人,如果他能胜利,那么那时候两堆剩余的石子数目一样或者有一堆已经被取完,他才能获胜利.

而对方为了赢,不可能把两堆的石头数目取得一样,所以忽略这种情况,也就是只剩下一种情况,那个输的那个人被逼得不得不把其中一堆取完.另一个人才能赢.

2,证明,现在假设一种情况,假如x>y,a人先取,b人后取,假设b后取的人必胜是,那么当a先取的人随便取一颗的时候并不影响两堆的结果,仍然是一堆比另一堆多,那么a先取的人仿佛又成为了后手,也就是说a前取的人会赢,同b后取的人胜利是矛盾的.

所以先取的人必胜利

3,而我找到了一种先取人必胜利的方法, 有x y两堆,你只需要把多的那一堆取剩的石头数目比第一堆少或者多一颗,无论你的对手怎样拿,你只需按第一种取法去调整两堆的数量,一直下去,会发现最后的结果是1 2此时候你是后手,先手无论怎么拿,你都胜利了

因此先取的人必胜利

不知道想法有没错误,请高手门指点

楼上好像不对。

对于2，对不同的具体的x和y应该具体讨论，不能只泛泛而谈 x>y， 这样只能说明，b不是永远必胜的。

对于3，如果我们把堆数取成两堆只相差1，对手只要同时去掉 少的堆的数目-1 的石头， 就成为2 1， 我们就输掉了。

不过我认为寻求稳态的办法是可以考虑的。。原题就是这样解的嘛（没有同时取石子的项)。 不过 改过之后变化很大，不一定有以前那么漂亮的解法了。

。。。晚了，明个儿再考虑。

[此贴子已经被作者于2007-7-29 0:22:58编辑过]

这是个小时候的游戏,游戏的规则似乎是取最后一个石子者失败.

游戏的基本技巧是,当你拿的时候,两堆石子是相等的话(不含每堆石子为1的情况),那就是输定了.所以如果你去拿时,只要把两堆石子的数量保持一致,便能赢.

我来解决这个问题

0 0 相差0

1 2 相差1

3 5 相差2

4 7 相差3

6 10 相差4

8 13 相差5

9 15 相差6

11 18 相差7

12 20 相差8

14 23 相差9

16 26 相差10

17 28 相差11

19 31 相差12

21 34 相差13

22 36 相差14

24 39 相差15

如此至无穷，每组的小数是尚未使用过的最小的数字。

这样的堆数可以说是 “死棋” 被“将军”

当堆数在这样的数列中时，后取者胜。

在其他情况时，先取者胜，他只需把堆数取成数列中的形式即可。

原因是这样。 条件规定的两种取法的意义是 在任何一堆出现0这个数，或两堆相差为0时。先取者胜。所以从最小数和相差数两方面入手考虑。 先前的帖子也注意到1 2 是“将军”，也就是说，当两堆不是1 2时，而两堆中任一堆出现1或2，或两堆相差1时，先取者能“将军”，必胜。

在此基础上，选3（剩下的数中最小的数）做基数，加2， 得到数组 3 5. 先取者无论如何取，要么出现0，1，2，要么两堆相差数成为0，1。后取者能将军。 所以3 5也是“死棋”

所以考虑这样数对的规律。 首先需要有没使用过的数中最小的。这样对手若是在这堆中取走石子。选手可以可以从另一堆中取走石子让它变成更低阶的“死棋”形式。 比如8 13，若对手取成7 13， 我们可以取成 7 4，继续“将军”

第二个条件是相隔数目逐对递增。这样对手从数目多的堆数取走石子时，会让两堆差距缩小。进入我们的“射程”，比如9 15，对手取成9 14，我们可以同时取走1，8 13继续“将军”

当对手从数目多的堆数拿走很多石头，使两堆差距发生逆转时，这时候的调整有些不一样。比如22 36， 如果对手取成22 13，我们可以调整为8 13， 若对手取成 22 14，我们可以同取2为12 20。总能调整成功，证明比较复杂，放后面。

解法部分到此结束。

但是另外需要注意的是

这样的数对可以覆盖整个整数集合。这个显然。

需要一一对应，在这种解法中 随着数字增大，基数在增大，两堆相差也在增大。所以后面的数不会和前面的数重复，能保证一一对应。 比如8+5=13严格 <9 +6。

解法的唯一性 。解法并不唯一，比如11 7，我们可以调整为4 7 或10 6，都是“将军”。

数对的特性。 这数列有奇怪的性质，初期有些类似费波拉其数列的性质。但很不一样。 1.较小数似乎以单独一个 连续两个 为单位，以奇怪的节奏进行反复。2. 他能保证后面证明的那个性质。

最后的证明：当较大的数a变为较小数c的时候，我们有两种方法调整。 一是他们相隔较近的时候，同时取走一定数目，比如22b 14c,这时它们相距8， 14的搭档是23，22无法达到，同时取走2变成20 12，是“死棋”。 二是他们相隔较远，比如22b 11c，相距11，相距11的死棋是17 28，无法达到。所以调整为18 11。

需要证明的是这两种方法覆盖的数字没有遗漏（偶尔有重复，如11 7）。考虑a b,a>b,如22 b 在所有“死棋”数列中寻找最小的较大数，使之大于a。对22来说，是14 23这一对。也就是说，对于b为14以下的数字时，22都可以用上面的方法2调整。考虑14 23 （相隔9）的前一对 12 20（相隔8） ，也就是说相隔8以内的数字，22都可以用方法1调整。 而23>22 9-8=1是最小的相差数, 所以 14=23-9>=22-8=14。 前一个14是方法2覆盖的范围，后一个14是方法1覆盖的范围。 范围没有遗漏。即证。

原创，欢迎指正，提问，改进。

[此贴子已经被作者于2007-8-17 13:38:36编辑过]

最原始的题目是这样

有三堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，一次可以在任意的一堆中取走任意多的石子；最后把石子全部取完者为胜者。假设双方都采取最好的策略，先取者是胜者还是败者。（PS：不同的两堆石子数目，应该会有不同的结论）

这题的解法是经典了。 先把三堆石子数目写成二的幂相加的形式，比如 9=1+8， 6=2+4。 这样，策略是，每一次尽量让每一个2的幂数都是偶数个，比如1 2 3， 2 4 6 ， 9 3 10。 当对手破坏这种平衡时，我们就去修复它，整个游戏就尽在掌握之中。

而把石头取完者是胜或是负并不重要，只要最后留意一下即可。战略不变。比如在2 1的时候，你应该取成0 1或1 1。

上一个题目也是这样，虽然相差不小，但多多少少都有寻找稳态的思想。 如果上一个题目改成取完着负，我想数列应该是0 1， 2 4，3 6这样吧。

关于这个经典解法，其实我还考虑过一些的。 为什么要取2的幂数；如果堆数增加，会不会变成3的幂数？ 大家不妨动动脑筋。2在这里似乎有很独特的性质。覆盖全面，结构稳定，又变化丰富。为什么只有2有这样的性质，难道仅仅因为2的高次幂=比它低的幂的和+1？我还没有让我满意的答案。。。