捡石头游戏

问题描述:

(捡石头游戏)一共有五堆石头，石头的个数依次是3，5，7，19，50。甲乙双方轮流从任意一堆中挑选(一次只能拿一堆，拿最后一块石头的获胜。A先拿，问A有没有胜算策略(就是不管B怎么拿，只要不出错A就能赢)。

分析:

这是一个数论中的最优策略问题，没有平均原理。

我会考虑一下，然后给你一个答复。

我要上班了，下班后我会继续思考...(没有太多时间回复，请见谅)

1.从50中取32片，剩余18片是正确的。

2.算法:从一堆中取n，这样剩下的所有数字都只是“一个输局(此时先取后输的情况)”。

3.所谓“负博弈”，就是把每一堆剩余的数转换成二进制数，然后把它们加在一起，规定无进位的加法(即异或运算)，即0+0 = 0，1+0 = 0，0+1 = 1。

4.“输局”原则:一个“输局”如果一次改变任何一个数字，就不再是“输局”。同时，任何“败局”都一定会通过正确减少某个数字而成为“败局”，而这个操作是唯一的。想象一下，现在是一场“败局”。如果你先拿了，势必会把某个数字1换成0，0换成1，肯定不再是“败局”，我也肯定能换成“败局”。实际上，这种情况相当于偶数。你拿了，肯定有对应我的，所以我一定要拿最后一个。简单的想，如果只有两堆，那么如果不相等，就是“输棋”。第一个拿走它们的人有获胜的方法。多拿几堆，让两堆相等，然后你拿几堆，我从另一堆拿几堆。

5.应用:(可能格式会变)

19 010011

7 000111

5 000101

3 000011

010010 (18)10

即需要18才能成为“败局”，所以50-18 = 32。

所以在1的时候，第五堆石头只能取出32粒，取出32粒后就是“负局”，也就是异或运算的结果是0。