丑妹和idiot过生日解答

丑妹和idiot过生日时玩分石子游戏。桌上有一堆石子，共103个。（两人岁数之积为103。）两人轮流分，每人可以选一堆至少有4个石子的，（两人岁数之差为4，）任意分成两堆。如果所有堆都少于4个就输了。先分赢还是后分赢？

这个问题要求出通解才行。设有很多个至少有4个石子的堆，考虑每堆石子数除4的余数。设a_0,a_1,a_2,a_3为余数为0，1，2，3的堆数。则一个状态是负状态的充分必要条件是a_0,a_1,a_2同为偶数或同为奇数。可以慢慢的证明从一个胜状态出发，一定可以到达一个负状态，而从一个负状态出发，一定不能到达另一个负状态。等最后a_0,a_1,a_2,a_3都变成0的时候有负状态的人就输了。

对于现在的初始条件，a_0,a_1,a_2为0,a_3为1，因此是负状态。先走的人输。

这一类游戏都是NIM游戏（三堆3，5，7个石子的游戏）的变化与推广。等过年以后我有时间时，想写一篇文章系统地介绍一下。

对了，你们两个到底几岁了？

所有跟帖： 

• pack! -idiot94- ♂ (2318 bytes) () 12/20/2006 postreply 17:48:02