取石子游戏
发布网友
发布时间：2022-04-30 15:43
共5个回答
热心网友
时间：2022-06-26 15:21
(1,1)时，显然先取者必败。
(1,2)时，先取者必胜，他可以在2那一堆中取1个，于是变成(1,1)，但这成为上一种情况了，于是接下来取的人必败，亦即先取者必胜。
(1,3)时，先取者必胜。他可以在3那一堆中取2个，于是变成(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)，对手必胜。
他从3那一堆中取2个，就变成了(1,2,1)，对手必胜。
他将3那一堆全部取走，就变成了(1,2)，对手必胜。
这些胜负有什么规律呢？我们可以将每堆的数转换成二进制，然后看每一位上所有堆里的1的个数总和：
必胜情况：(n) (1,2)(1,3)(2,3) (1,1,1)(1,1,2)(1,2,2)
必败情况： (1,1)(2,2)(3,3) (1,2,3)
化为二进制：
必胜情况：
(n)<只有1堆>：……（反正每位只要有1肯定只有1个）
(1,2)：1,10
列成竖式：
01
10
个位上只有1个1，“十位”（因为是二进制所以叫十位不妥，这里为了方便说明暂且使用，下同）上也只有1个1。
(1,3)：1,11
列成竖式：
01
11
个位上有2个1（1的1个，3的1个），十位上有1个1。
(2,3)：10,11
个位上有1个1，十位上有2个1。
(1,1,1)：1,1,1
个位上有3个1。
(1,1,2)：1,1,10
个位上有2个1，十位上有1个1。
(1,1,3)：1,1,11
个位上有3个1，十位上有1个1。
(1,2,2)：1,10,10
个位上有1个1，十位上有2个1。
必败情况：
(1,1)：1,1
个位上有2个1。
(2,2)：10,10
十位上有2个1。
(3,3)：11,11
个位上有2个1，十位上也有2个1。
(1,2,3)：1,10,11
个位上有2个1，十位上也有2个1。
下面分析一下这些情况。
先看必败情形。容易发现，所有的必败情形，都是所有的数位上都有偶数个1。
下看必胜情形。我们发现，出现了两种情况：
1.只有1位上有奇数个1，如(1,3)(2,3)(1,1,1)(1,1,2)(1,2,2)。而先取者取走该位上的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的个数是偶数即可（一种简单的方法是，他在一堆中取几个，你在另一堆中也取几个就可以）。
热心网友
时间：2022-06-26 15:21
热心网友
时间：2022-06-26 15:22
热心网友
时间：2022-06-26 15:22
热心网友
时间：2022-06-26 15:23
