取石子游戏

Light

两个人做取石子游戏，有若干堆石子，每堆都有若干个，两个人轮流取石子，有两种取法：1.在一堆中取任意数量棋子，2.在两堆中取相等数量棋子。取最后一个棋子的人输（也就是说要留给对方最后一个棋子就赢了），如果你是先手，求出在什么情况下必胜，以及必胜方案。
请给予详细讲解，包括必胜的方案中取十字数目的算法，谢谢！

ggglgq

　　
  
   
    提供一个与本主题相关的主题： 小游戏,谁能取胜
  
    http://bbs.mf8-china.com/viewthread.php?tid=764
  
　　
　　

Light

能不能说的详细一点……

Paracel_007

(1，2)是先行必胜态啊

phileas

楼上的答案有点问题：通项公式是[(1+sqrt(5))n/2], [(3+sqrt(5))n/2]，二堆先行必输态的前两个是(1,2), (3,5)

三堆没法套用二堆的做法，第一个先行必输态是(1,1,1)

lulijie

归纳一下：
二堆必败态按从小到大的顺序，记作f(n)。
那么，f(1)=(0,1)
         f(2)=(2,2)
初始集合A={3，4，5，6，7，......)
n>=3的所有的必败态f(n)，可以用以下递推公式推出：min(A)表示A集合中的最小元素。
          f(n)=( min(A)，min(A)+n-1)
         A=    A 删除元素 min(A)  和  min(A)+n-1

tm__xk

差点忘了还有N堆的情况........= =||||

lulijie

两堆的必败态：
自然数集：1，2，3，4，5，6，7，,.........................
差值集合：0，1，2，3，4，5，6..........
-------------------------------------
首先：(0,1)   差值为1
自然数集删去1，差值集合删去1
变成：
自然数集：2,3,4,5,6,7,.........................
差值集合：0，2，3，4，5，6..........
------------------------
然后从自然数集选最小的数为2，差值集合选择最小的数为0，
得到第二个必败态为(2,2)
自然数集删去2，差值集合删去0
变成：
自然数集：3，4，5，6，7，8，.......................
差值集合：2，3，4，5，6..........
--------------------------------------------------
然后从自然数集选最小的数为3，差值集合选择最小的数为2，
得到下一个必败态为(3,5)
自然数集删去3和5，差值集合删去2
变成：
自然数集：4，6，7，8.........................
差值集合：3，4，5，6..........
----------------------------------------------------
然后从自然数集选最小的数为4，差值集合选择最小的数为3，
得到下一个必败态为(4，7)
自然数集删去4和7，差值集合删去3
变成：
自然数集：6，8，9.........................
差值集合：4，5，6..........
------------------------------------------------------
然后从自然数集选最小的数为6，差值集合选择最小的数为4，
得到下一个必败态为(6，10)
自然数集删去6和10，差值集合删去4
变成：
自然数集：8，9，11，12........................
差值集合：5，6，7，8..........
-------------------------------------------------
依次类推，得出
（8，13），（9，16），（11，18）。。。。。。

[ 本帖最后由 lulijie 于 2010-2-15 23:43 编辑 ]

tm__xk

看来中学的东西都忘光了....原来还有Beatty定理这种东西....

tm__xk

哦........原来如此..
开始几项不对..