抓三堆问题可以用二进制方法来解决么

抓三堆问题可以用二进制方法来解决么

能 二进制法解“抓三堆”问题抓三堆
有三堆谷粒（例如100粒、200粒、300粒），甲、乙轮流抓，每次只能从一堆中抓，最少抓1粒，可抓任意多粒；甲先抓，规定谁抓到最后一把谁赢。问：甲应该如何抓？为什么？
分析：问题特殊化
1、只有一堆时，即状况为（a , 0 , 0）,此时先抓者必胜
2、只有两堆时，即状况为（a , b , 0）
（1）若b = a , 即状况为（a , a , 0）,此时后抓者必胜。因为
对方先抓后，结果或剩一堆，成为（a , 0 , 0）的状况，
一把可抓完；或剩两堆，你抓后，又成为新的（d , d , 0）
的状况，且d < a , 继续由对方抓。
（2）若b ≠ a ,不妨设b > a ,即状况为（a , b , 0）, 此时先抓
者必胜。因为先抓者可以把第二堆抓掉b – a个，使状况
转化为（a , a , 0）, 成为新的“状况（1）”。
3、三堆都有，且其中两堆相等，即状况为
（a , a , c）,此时先抓者必胜。因为先抓者可以把
第三堆全抓完，使状况转化为（a , a , 0）,成为新
的“状况 2)（1）”。
4、三堆都有，且其中任意两堆都不相等，即状况为（a , b , c）, 且不妨设a < b < c ,此时情况比较复杂。
为了下面表述得清楚，我们把前面的一个结论用“反面说法”，总结为
“把两堆相等的状况留给对方，自己可以取胜。”
然后再讨论 a、b、c 的不同情况。以其中最小的a为“主要线索”分情况讨论。
（1）a ＝ 1 时，即状况为（1 , b , c）。
下面再对 b 分情况讨论。
（2）a ＝ 2 时，即状况为（2 , b , c）。
下面再对 b 分情况讨论。
（3）a ＝ 3 时，即状况为（3 , b , c）。
下面再对 b 分情况讨论。
（4）a ＝ 4 时，即状况为（4 , b , c）。
下面再对 b 分情况讨论。
然后再讨论 a、b、c 的不同情况。以其中最小的a为“主要线索”分情况讨论。
（1）a ＝ 1 时，即状况为（1 , b , c）。
下面再对 b 分情况讨论。
（2）a ＝ 2 时，即状况为（2 , b , c）。
下面再对 b 分情况讨论。
（3）a ＝ 3 时，即状况为（3 , b , c）。
下面再对 b 分情况讨论。
（4）a ＝ 4 时，即状况为（4 , b , c）。
下面再对 b 分情况讨论。
（1）a ＝ 1 时，即状况为（1 , b , c）。下面再对 b 分情况。
由于a < b < c ,即 a、b、c “前小后大”，因此 b最小为2，于是起始情况是（1 , 2 , 3）。经用“穷举法”分析，该情况下后抓者胜；或用“反面说法”说成，“把（1 , 2 , 3）的状况留给对方，自己可以取胜”。
下一个情况是（1 , 2 , c）, c > 3 。此时必先抓者胜。因为先抓者只要把第三堆抓剩3个，就转化成（1 , 2 , 3）的状况，从而必胜。
下一个情况是（1 , 3 , c）, c > 3。此时必先抓者胜。因为先抓者只要把第三堆抓剩2个，就转化成（1, 3 , 2）的状况，也即（1, 2 , 3）的状况，从而必胜。
下一个情况是（1 , 4 , c）, c > 4。起始情况是（1 , 4 , 5）。经用“穷举法”分析，该情况下后抓者胜；或用“反面说法”说成，
“把（1 , 4 , 5）的状况留给对方，自己可以取胜”。
这样类似地分析下去，逐渐可以得到结论：
把（1 , 2 , 3）的状况留给对方，自己可以取胜。
把（1 , 4 , 5）的状况留给对方，自己可以取胜。
把（1 , 6 , 7）的状况留给对方，自己可以取胜。
把（1 , 8 , 9）的状况留给对方，自己可以取胜。
这样类似地分析下去，逐渐可以得到结论：
把（1 , 2 , 3）的状况留给对方，自己可以取胜。
把（1 , 4 , 5）的状况留给对方，自己可以取胜。
把（1 , 6 , 7）的状况留给对方，自己可以取胜。
把（1 , 8 , 9）的状况留给对方，自己可以取胜。
于是归纳、抽象、猜测：把（1 , 2m , 2m+1）的状况留给对方，自己可以取胜。
然后用数学归纳法可以证明，这一结论是正确的。【自己证明】
这样，就把 a ＝ 1 时的情况，全搞清楚了。
（2）a ＝ 2 时，即状况为（2 , b , c）。
下面再对 b 分情况。
由于a < b < c , 即a、b、c “前小后大”，因此 b最小为3，于是起始情况是（2 , 3 , c）。c > 3。
此时必先抓者胜。因为先抓者只要把第三堆抓剩1个，就转化成（2 , 3 , 1）的状况，也即（1 , 2 , 3）的状况，从而必胜。
下一个情况是（2 , 4 , c）, c > 4。起始情况是（2 , 4 , 5）。此时必先抓者胜。因为先抓者只要
把第一堆抓剩1个，就转化成（1 , 4 , 5）的状况，从而必胜。
下一个情况是（2 , 4 , 6）。经用“穷举法”分析，该情况下后抓者胜；或用“反面说法”说成，“把（2 , 4 , 6）的状况留给对方，自己可以 取胜”。
这样类似地分析下去，逐渐可以得到结论：
把（2 , 4 , 6）的状况留给对方，自己可以取胜。
把（2 , 5 , 7）的状况留给对方，自己可以取胜。
把（2 , 8 , 10）的状况留给对方，自己可以取胜。
把（2 , 9 , 11）的状况留给对方，自己可以取胜。
于是归纳、猜测：把（2 , 4m , 4m+2）或（2 , 4m+1 , 4m+3）的状况留给对方，自己可以取胜。然后用数学归纳法可以证明，这一结论是正确的。
这样，就把a = 2 时的情况，全搞清楚了。
（3）a ＝ 3 时，即状况为（3 , b , c）。
下面再对b分情况。类似地分析下去，逐渐可以得到结论：
把（3 , 4 , 7）的状况留给对方，自己可以取胜。
把（3 , 5 , 6）的状况留给对方，自己可以取胜。
把（3 , 8 , 11）的状况留给对方，自己可以取胜。
把（3 , 9 , 10）的状况留给对方，自己可以取胜。
于是归纳、猜测：
把（3 , 4m , 4m+3）或（3 , 4m+1 , 4m+2）的状况留给对方，自己可以取胜。然后用数学归纳法可以证明，这一结论是正确的。这样，就把a = 3 时的情况，全搞清楚了。
为了赢律更大，还需研究 a =4 时的情况，a = 5 时的情况
例如a ＝ 4 时的情况，经过研究可以得到结论：
把（4 , 8 , 12）的状况留给对方，自己可以取胜。
把（4 , 9 , 13）的状况留给对方，自己可以取胜。
把（4 , 10 , 14）的状况留给对方，自己可以取胜。
把（4 , 11 , 15）的状况留给对方，自己可以取胜。
把（4 , 16 , 20）的状况留给对方，自己可以取胜。
把（4 , 17 , 21）的状况留给对方，自己可以取胜。
把（4 , 18 , 22）的状况留给对方，自己可以取胜。
把（4 , 19 , 23）的状况留给对方，自己可以取胜。
于是归纳、猜测：
把（4 , 8m , 8m+4）或（4 , 8m+1 , 8m+5）或（4 , 8m+2 , 8m+6）或（4 , 8m+3 , 8m+7）的状况留给对方，自己可以取胜。
然后用数学归纳法可以证明，这一结论是正确的。
这样，用“数列通项公式”的方法，继续研究
下去，也能得出取胜的策略，但表达起来会很繁琐。
因为已经看到，在（a , b , c），a < b < c的
规定下，
a ＝ 1 时，有一种表达式（1 , 2m , 2m+1）的状况留给对方，自己可以取胜。
a ＝ 2 时，有二种表达式（2 , 4m , 4m+2）或（2 , 4m+1 , 4m+3）的状况留给对方，自己可以取胜。
a = 3 时，有二种表达式（3 , 4m 4m+3）或（3 , 4m+1 , 4m+2）的状况留给对方，自己可以取胜。
a = 4 时，有四种表达式（4 , 8m , 8m+4）或（4 , 8m+1 , 8m+5）或（4 , 8m+2 , 8m+6）或
（4 , 8m+3 , 8m+7）的状况留给对方，自己可以 取胜。
可以猜测，a ＝ 4、5、6、7这四种情况时，都分别有四种通项表达式的状况留给对方，自己可以取胜。
a ＝8、9、10、11、12、13、14、15这八种情况时，都分别有八种通项表达式的状况留给对方，自己可以取胜。
…………
a ＝ 2k ，2k+1，2k +2，…，2k+1-1 ，这 2k种情况时，都分别有 2k种通项表达式的状况留给对方，自己可以取胜。
“抓三堆”的二进制解法
用二进制表示这三堆谷粒数，写成三行，并上下对齐，各列相加，列的加法定义为0+0=0；0+1=1；1+0=1；1+1=1.
这就是模2加法。（只要是有2的倍数，就都可以作为0）
关于模2加法，可以推广；比如推广为模7加法：
例1：如果1号是星期一，问 27号是星期几？
解答：27号与1号相差26天，因为 26=7*3+5. ，说明过去3个7天之后，再过5 天，这样27号这天就是星期一再加上5天，即星期六。（事实上，这里只要是有7的倍数，就都可以作为0。）
例2：如果1号是星期三，问 27号是星期几？（答：星期一）
我们断言：把三堆谷粒数均表为二进制，写成三行，将位数对齐，各列“模2相加”，若各列的和全为0，则后抓者有必胜策略； 若和中出现1，则先抓者有必胜策略。
和中出现1时，先抓者的具体策略是：先抓者从最左边的1所在的列，寻找某堆的谷粒数中相应的列也有1，就从该堆中抓走适当个数，使得抓完后各列的和（模2）为0。
一、由于谷粒数越来越少，最后，先抓者可以使得后抓者始终面临各列模2之和为（0，0，…，0）状态，这意味着先抓者获胜。
二、后抓者只要抓，谷粒就将减少，因此该行中至少有一个1变为0（如果1都不变为0，只会使谷粒数增加或不变），从而该列模2之和将为1。于是先抓者就不会面临（0，0，…， 0）状态。
三、先抓者的正确抓法，应使得各列模2之和均为0。即，先抓者应总是抓成（0，0，…， 0）状态。
例1：设原始状态（2，3，4），则先抓者胜。
例2：设原始状态（5，8，13），则后抓者胜。
例3：设原始状态（5，12，13），则先抓者胜。