【例 7】桌上有两堆棋子，分别有12粒和28粒，甲乙两人轮流从其中的一堆里取出若干粒，不能同时在两堆中都取，也不能不取．-奥数库

题目与解析

问题

【例 1】桌上有两堆棋子，分别有12粒和28粒，甲乙两人轮流从其中的一堆里取出若干粒，不能同时在两堆中都取，也不能不取．且取出的棋子数必须是另一堆棋子数的约数．取到最后一粒者为胜．如果甲先取， ____________采用正确的策略，必胜．

答案与解析

从棋子数较少的时候开始分析．如果两堆棋子个数相等，则后取的一方有必胜策略，先取的一方从一堆里面取几个，后取的一方就可以从另一堆里面取几个．如果较少的一堆只有1个棋子，则如果取走这个棋子，对方必胜（任何数都是0的约数，可以一次取走），所以只有取较多的一堆的棋子，而且只能取1个，所以可以分析出，较多的一堆有奇数个棋子时，后取者有必胜策略；较多的一堆有偶数个棋子时，先取者有必胜策略．如果较少的一堆有2个棋子，此时如果较多的一堆有奇数个棋子，根据前面的分析，先取者可以从2个棋子的一堆中取走1个而获胜；如果较多的一堆有偶数个棋子，根据前面的分析，如果一方从某一堆中取走奇数个棋子，则对方有必胜策略；如果从较多的一堆中取走2个棋子，则可以分析出，较多的一堆棋子数被4除余2时，后取者有必胜策略；较多的一堆棋子数被4整除时，先取者有必胜策略．继续分析，可总结一般规律：如果两堆棋子数目写成二进制后，末尾0的个数相等(包含同为0个，也就是都是奇数的情况)，则后取的一方有必胜策略，否则先取的一方有必胜策略．考虑二进制表达式，分别是1100和11100．0的个数相等，所以乙有必胜策略．如果两堆的末尾0的个数相等，例如都有个．则从一堆中取的棋子数目末尾的0至多个．如果取的棋子数目末尾的0个数为，则相减后会发现所得的差的末尾0的个数超过；如果取的棋子数目末尾的0个数小于，则相减后会发现所得的差的末尾0的个数也小于n．所以，从0的个数相等的状态取一次只能到达0的个数不相等的状态．另一方面，从0的个数不相等的状态，总可以从0较多的一堆取出和0较少的一堆的0个数一样多的棋子，这样两堆末尾0的个数就一样多了．