取币游戏(二)

lulijie

有个取币游戏：
开始时在六个盒子B1,B2,B3,B4,B5,B6中各有一枚硬币，每次操作允许如下：
        ①选一个不空的盒子Bj(j<6)，取出Bj中的一枚硬币，在B(j+1)中加两枚硬币；
或者②选一个不空的盒子Bk(k<5)，取出Bk中的一枚硬币，并交换B(k+1),B(k+2)中的硬币(可能是空的)。
-------------------------------------------------------------------------------------------------------
现在有两个人轮流取币，若轮到取币的人无法取币时，他就算输。
那么是先取方胜，还是后取方胜？

lulijie

此贴是看到 2010年IMO试题 第5题后突然想到的。
当时我也没答案。
经过这几天的思索，昨天晚上作出了答案，睡觉时一直考虑为什么是这结果，最后突然一下子想通了。
下面我把我的解题思路说一下，希望对大家有帮助。
-------------------------------------------------------------------------------
先假设一般情况，一共有m个盒子，每个盒子的硬币数任意个。
因为无论哪种操作方法，操作的箱子的硬币数目都是减1，变化的是它后面的箱子。所以演变到最后，一定会归结为两个箱子的问题。
----------------------------------------------------------------------------
对于 两个箱子，硬币数为b，a
     那么先手方必败局面是 b为偶数。 最后变为0，x 的形式，先手方无币可取。
-------------------------------------------------------------------------------------
再往前推导到三个箱子   c，b，a          按照c、b、a的奇偶一共有8种情况
     必败局面为 奇奇奇，偶偶奇，偶偶偶
-----------------------------------------------------------------------------------------
再推导到四个箱子   d，c，b，a  
    必败局面为 偶奇奇奇，偶偶偶奇，偶偶偶偶，奇奇偶偶，奇偶奇奇，奇偶奇偶
                 或简写成    偶*(奇奇奇+偶偶奇+偶偶偶)，奇*(奇偶偶+偶奇奇+偶奇偶)
---------------------------------------------------------------------------------------
再推导到五个箱子   e，d，c，b，a  
    必败局面为     (奇奇+偶偶)*(奇奇奇+偶偶奇+偶偶偶)，(偶奇+奇偶)*(奇偶偶+偶奇奇+偶奇偶)
---------------------------------------------------------------------------------------
一直往前推导，最后归纳出的结论是：
对于m个箱子，硬币数分别为 a1，a2，......，a(m-3)，a(m-2)，a(m-1)，a(m)
      那么必败局面是
          若     a1+a2+......+a(m-3)  为偶数，则a(m-2)，a(m-1)，a(m)为  奇奇奇或偶偶奇或偶偶偶
          若     a1+a2+......+a(m-3)  为奇数，则a(m-2)，a(m-1)，a(m)为  奇偶偶或偶奇奇或偶奇偶
        其余的都是必胜局面。
------------------------------------------------------------------------------
为什么会是上面的结果，说穿了道理非常简单。我暂时卖个关子，让大家想想。

[ 本帖最后由 lulijie 于 2010-7-26 19:42 编辑 ]