威佐夫博弈，两人同时取石子的问题，怎么和黄金分割扯上了关系？

今天是算法和数据结构专题第25篇文章，我们继续博弈论专题。

在上一篇文章当中我们了解了简单的巴什博奕，今天我们来看看另一个经典的博弈模型——威佐夫博弈。博弈论和机器学习有些类似，数学家们针对场景进行建模，设计出了几个经典模型。然后我们在面临具体问题的时候，对问题进行深入分析，寻找合适的模型应用来解决它。

石子问题

我们来看一道经典的例题，有两堆石子，有两个绝顶聪明的人在玩一个游戏。每次每个人可以从其中一堆石子当中取走任意数量的石子，或者是从两堆当中同时取走相同数量的石子。无法取石子的人落败，请问，在告知两堆石子数量的情况下，这两个人当中哪一方会获胜？

我们简单分析一下，会发现一些局面是先手必败的。比如说(0, 0)，再比如(1, 2)。我们简单分析一下(1, 2)，先手有4种策略，首先他可以取走堆，那么后手可以取完第二堆，显然后手获胜。他也可以在第二堆当中取1个，这时剩下(1, 1)，后手会同时取完，同样是后手获胜。第三种是他取走第二堆，后手可以取完堆，后手获胜。第四种是他在堆和第二堆当中同时取走一个，这时第二堆剩下一个，后手胜。

那么，这些必败的状态之间有什么规律呢？我们怎么找到这个规律，并且找到解呢？

分析

我们可以枚举几个必败的状态：(0, 0), (1, 2), (3, 5), (4, 7)...

我们观察一下这些状态，可以找到两条规律。我们假设从小到大排的第k个必败状态是(x, y)，并且x < y。我们可以发现y = x + k。也就是说必败状态两个数的差值是递增的，这也说明了每一个必败状态的差值都各不相同。

其实这是很容易证明的，我们用反证法，假设(a, a+k), (b, b+k)都是必败状态，并且a < b。那么先手在面临(b, b+k)的时候，只需要在两堆当中同时取走b-a个石子，那么给后手的局面就是(a, a+k)。对于后手来说，这是一个必败的局面，这就和(b, b+k)先手必败矛盾，所以不存在两个必败局面的差值相等。

我们也可以作图分析，我们把两堆石子的数量看成是坐标轴上的一个点。所以游戏就变成了：棋盘上有一个点，每次每个人可以将它向下、向左或者向左下移动若干个格子，不能移动的人输。终止节点显然是原点，一步就能移动到原点的点显然是必胜点，假设我们给这些所有必胜点都染色的话，剩下的点当中横纵坐标和小的点就是下一个必败点。因为它不论如何移动，都会给对手留下一个必胜点。

我们根据上面的逻辑把必败点都染色，可以得到下面这张图：

从这张图可以看出，必败点之间不能通过一次移动得到，换句话说可以一次移动到必败点的点都是必胜点，从图上可以看出，除了必败点的之外的点都是必胜点，并且每一个自然数都必然只会被包含在一个必败状态当中。

到这里，我们距离解法已经很接近了，现在剩下的问题是，我们如何根据x和y的取值快速判断它们是否构成一个必败局面呢？也就是说我们能不能找出一个通项公式，对于第k个必败局面，它的坐标是()呢？

求解

为了写出通项公式，我们需要引入Betty定理。

“

设a和b是两个正无理数，并且

记P={[], }, Q={[], }，则，

证明