取火柴游戏

问题1:有若干堆火柴,两人依次从中拿取,规定每次只能从一堆中取若干根, 可将一堆全取走,但不可不取,最后取完者为胜,求必胜的方法。

问题2: 今有若干堆火柴,两人依次从中拿取,规定每次只能从一堆中取若干根,可将一堆全取走,但不可不取,最后取完者为负,求必胜的方法。

这是一道博弈题,但是胜负判定方法不同使得解决他们的方法也大有不同。

问题1

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

对于问题1有如下这些定理。

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

[定理2]:T态,取任何一堆的若干根,都将成为S态。

[定理3]:S态,只要方法正确,必赢。

[定理4]:T态,只要对方法正确,必败。

故只需异或每一堆的火柴数量,为0必败,为1必胜。

问题2

定义:若一堆中仅有1根火柴,则被称为孤单堆。若大于1根,则称为充裕堆。

充裕堆个数大于等于2的后缀为2;充裕堆个数为1的后缀为1;充裕堆个数为0的后缀为0。以此产生T2、T1、T0及S2、S1、S0。(需注意充裕堆为1的话不存在火柴堆是的总异或为0,即T1不存在。)

对于问题2有如下这些定理。顺序由简单向复杂递推。

[定理1]:S0态,即仅有奇数个孤单堆,必败。T0态必胜。

[定理2]:S1态,只要方法正确,必胜。

[定理3]:S2态不可转一次变为T0态。

[定理4]:S2态可一次转变为T2态。

[定理5]:T2态,只能转变为S2态或S1态。

[定理6]:S2态,只要方法正确,必胜.

[定理7]:T2态必输。

由此,我们可以得到结论:

 必输态有:T2,S0

 必胜态:S2,S1,T0

小结

第一题的全过程其实如下:

S2->T2->S2->T2-> …… ->T2->S1->T0->S0->T0->……->S0->T0(全0)

第二题的全过程其实如下:

S2->T2->S2->T2-> …… ->T2->S1->S0->T0->S0->……->S0->T0(全0)

问题2在hdu上有

HDU1907