nim游戏以及证明过程

参考资料  (后面的证明写错了,差评,不要看,看图就好了)

 

  1. 题目1:今有若干堆火柴,两人依次从中拿取,规定每次只能从一堆中取若干根,

 

可将一堆全取走,但不可不取,最后取完者为胜,求必胜的方法。

 

题目2:今有若干堆火柴,两人依次从中拿取,规定每次只能从一堆中取若干根,

 

可将一堆全取走,但不可不取,最后取完者为负,求必胜的方法。

 

嘿嘿,这个游戏我早就见识过了。小时候用珠算玩这个游戏:第一档拨一个,第二档拨两个,依次直到第五档拨五个。然后两个人就轮流再把棋子拨下来,谁要是最后一个拨谁就赢。有一次暑假看见两个小孩子在玩这个游戏,我就在想有没有一个定论呢。下面就来试着证明一下吧

 

先解决第一个问题吧。

 

定义:若所有火柴数异或为0,则该状态被称为利他态,用字母T表示;否则,

 

为利己态,用S表示。

 

[定理1]:对于任何一个S态,总能从一堆火柴中取出若干个使之成为T态。

 

证明:

 

    若有n堆火柴,每堆火柴有A(i)根火柴数,那么既然现在处于S态,

 

      c = A(1) xor A(2) xor … xor A(n) > 0;

 

    把c表示成二进制,记它的二进制数的最高位为第p位,则必然存在一个A(t)(注:我觉得应该是必然存在奇数个),它二进制的第p位也是1。(否则,若所有的A(i)的第p位都是0,这与c的第p位就也为0矛盾)。

 

    那么我们把x = A(t) xor c,则得到x < A(t).这是因为既然A(t)的第p位与c的第p位同为1,那么x的第p位变为0,而高于p的位并没有改变。所以x < A(t).而

 

    A(1) xor A(2) xor … xor x xor … xor A(n) (需要注意的是,这里是没有A(t)这一项的,前面之所以要说明x<A(t),表达的意思是,之前是A(t),现在取了一个正数A(t)-x到x

 

  = A(1) xor A(2) xor … xor A(t) xor c xor … xor A(n)

 

  = A(1) xor A(2) xor… xor A(n) xor A(1) xor A(2) xor … xor A(n)

 

  = 0

这就是说从A(t)堆中取出 A(t) – x 根火柴后状态就会从S态变为T态。证毕

未命名

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz