如何赢得拿石头的游戏?
(1,1),很明显,先拿的人会失败。
(1,2),先拿的人赢。他可以在2的堆里拿1,所以就变成了(1,1),但这变成了前面的情况,所以接下来拿的人就输了,也就是先拿的人就赢了。
(1,3),第一个赢。他可以从三堆中取出两个,所以就变成了(1,1)。
(2,2),第一个拿的会失败。他任意一堆拿1,对方马上另一堆拿1,就成了(1,1);如果他拿走一堆中的所有石头,另一方拿走另一堆中的所有石头。
(2,3),第一个赢。他可以从3的堆里取1,所以就成了(2,2)。
(3,3),第一个拿的会失败。他从任意一堆中取1,2或者3,就变成了上面讨论的情况。
(1,1,1),谁先拿谁就赢。如果他取任意一堆,就变成(1,1)。
(1,1,2),先拿的人赢。他把那堆2拿走,就变成了(1,1)。
(1,1,3),先拿的人赢。他把那堆3拿走,就变成了(1,1)。
(1,2,2),第一个赢。他取了1的那堆,就成了(2,2)。
(1,2,3),谁先拿谁就失败。分析如下:
他先取1的那堆,就变成了(2,3)。从上面的分析来看,对手会赢。
他从2的堆里取1,就成了(1,1,3)。对手可以拿3的所有堆,就变成了(1,1),那么他就赢了。
他把2的堆都拿走了,就变成了(1,3),对手就赢了。
他从3的堆里取1,就变成了(1,2,2),对手就赢了。
他从三个的堆里拿两个,变成了(1,2,1),对手就赢了。
他把3的堆都拿走了,就变成了(1,2),对手就赢了。
这些胜败的规律是什么?我们可以把每一堆的数字转换成二进制,然后看看每一位上所有堆的数字之和1:
中奖情况:(n) (1,2) (1,3) (2,3) (1,1,1) (1,2)
失利情况:(1,1) (2,2) (3,3) (1,2,3)
转换为二进制:
获胜情况:
(n)& lt;只有1桩> :.....(反正每个人只要有1,就一定只有1)
(1,2):1,10
垂直位置的列:
01
10
单位位只有1 1,“十位”也只有1 1(因为是二进制,所以不太合适叫十位,这里为了方便使用,下同)。
(1,3):1,11
垂直位置的列:
01
11
十位数中有两个1(1的1和3的1)和1的1。
(2,3):10,11
单位里有1,十里有2个1。
(1,1,1):1,1,1
单位里有三个1。
(1,1,2):1,1,10
一位有两个1,十位有1。
(1,1,3):1,1,11
一位有三个1,十位有1。
(1,2,2):1,10,10
单位里有1,十里有2个1。
失败失败的情况:
(1,1):1,1
单位里有两个1。
(2,2):10,10
第十名有两个1。
(3,3):11,11
一位有两个1,十位有两个1。
(1,2,3):1,10,11
一位有两个1,十位有两个1。
我们来分析一下这些情况。
先看输的情况。很容易发现,所有输的情况在所有数字上都是1的偶数。
看赢的情况。我们发现有两种情况:
1.只有第1位有1的奇数,如(1,3) (2,3) (1,1,1) (1,65438)当第一个取者从这个位取1时,所有位都变成1的偶数,然后最后一个取者成为第一个取者。
2.若干位上有1的奇数,如(n) (1,2) (1,1,3)。第一个取了之后(不一定是哪个取了),所有的位都变成了1的偶数。最后一个人成为第一个人。
在这两种情况下,后来者都被迫陷入一种失败的境地,以取得胜利。
从上面的分析我们可以得出一个结论:把堆里的石头全部转换成二进制后,如果所有位数上的数字1都是偶数,那么先拿的那个就失败;如果某些位上的1的数是奇数,而第一个接受者能把所有位上的1的数变成偶数,那么第一个接受者就赢了。
好了,我们来分析一下我们的话题。
3,5,7,19,50变成二进制是:
000011
000101
000111
010011
110010
可以看出,只有最高阶的1是奇数,其他位都是偶数。
所以你只需要拿走1的最高位就赢了。
二进制100000在二进制10中是32,所以从那堆50块石头中拿走32,拿走了就变成偶数了。所以第一个拿到的人会赢。以后不管对方怎么取,都要保证每个位上的1的个数是偶数(一个简单的方法就是他一堆取几个,你另一堆也可以取几个)。