我在想是否有一种简单的方法可以看出这里的模式。我已经想了好几个小时了,还没能完整地表达出来。
游戏的运作方式是有两个玩家,N
石头塔,当轮到玩家时,他必须从塔中移除至少一块石头,移除最后一块石头的玩家获胜。
以下是我迄今为止画出的一幅塔楼高度图:
// {1} ---> "First" (remove the single stone)
// {2} ---> "First" (remove both stones)
// {n}, n > 2 ---> "First" (remove all the stones)
// {1, 1} ---> "Second" (because your only option is to remove 1 stone and then your opponent only has to remove 1 stone to win)
// {1, 2} ---> "First" (because you can remove 1 stone from the 2nd tower and then your opponent is left with {1, 1} which makes him lose as I explained in the last one)
// {1, 3} ---> "First"
// {1, n}, n > 1 ---> "First"
// {2, 2} ---> "Second"
// {2, 3} ---> "First"
// {2, 4} ---> "First"
// {2, n}, n > 2 ---> "First"
// {m, n} ---> m < n ---> "First"
// {1, 1, 1} ---> "First"
// {1, 1, 2} ---> "First"
// {1, 1, 3} ---> "First"
// {1, 1, n} ---> "First"
// {1, 2, 2} ---> "First"
// {1, 2, 3} ---> "Second"
// {1, 2, 4} ---> "First"
// {1, 2, 5} ---> "First"
// {1, 2, n}, n > 3 ---> "First"
// {2, 2, 2} ---> "First"
// {2, 2, 3} ---> "First"
// {2, 2, n}, n > 1 ---> "First"
我想到的事实:
如果每座塔有一块石头,轮到的玩家如果塔数为奇数,则获胜,否则失败
如果塔数
N
且任何塔的高度大于N+1
,则结果与该塔的高度N+1
相同除此之外,我无法找出足够的模式来写出线性解。
有什么帮助吗?
最佳答案
这个游戏叫做nim。获胜的策略是留下一个位置,每个塔中石头数量的异或为0。这将迫使对手转到具有非零异或值的配置。然后,第一个玩家可以再次到达一个xor值为0的位置。
例如,从{1,2,4}开始,一个成功的步骤是转到{1,2,3}。注意1 xor 2 xor 3=0。假设对手从最后一堆{1,2,1}中取出2块石头,下一个获胜的移动将完全移除第二堆:{1,0,1}再次使异或值为0;依此类推。