WythoffGame 威佐夫博弈

问题

$A$ 和 $B$ 两人轮流从苹果和梨子中取出水果，两堆水果的数量分别为 $p$ （苹果）和 $k$ （梨子）且 $p \ne k$ 。

每人每次既可以从一堆水果中取任意个水果（至少取 $1$ 个），也可以从两堆水果中同时取任意个水果（至少取 $1$ 个），取的数量没有上限，最后一个把水果取光的人获胜。

给定 $p, k$ ，当我方先手，我方和对方都是高手（在能赢的情况下一定能赢），求我方是否能赢。

解法

$(1)$ 当我方面临 $p = 2, k = 1$ 局势时，我方必输，因为我方无法一次把两堆物品取光，且必然留给对方局势 $(p, p)$ （ $p \ge 0$ ），对方可以一次将两堆物品取光；

$(2)$ 当我方面临 $p = 3, k = 1$ 局势时，我方取 $p = 1$ 时，留给对方 $p = 2, k = 1$ 局势，我方才赢；

$(3)$ 当我方面临 $p = 3, k = 2$ 局势时，我方取 $p = 1, k = 1$ 时，留给对方 $p = 2, k = 1$ 局势，我方必赢。对于所有的 $p = k + 1, 2 \le k$ 局势，我方从两堆物品中同时取 $k - 1$ 时必赢。

\cdots

把 $(2, 1), (3, 1)$ 这样的局势看作棋盘上的坐标时，很像“皇后的棋步”（Queen's Move）。

上图中 $(1,1), (2,2), (3,2), (2,3), (3,3), (3,4), (4,3) \dots$ 这些在虚线上的坐标，当我方面对这样的局势时必赢（称这样的局势为安全局势）。棋盘上关键的位置是红色的 $(1,2), (2,1), (3,5), (5,3) \dots$ ，这些是安全局势的边界点，当我方面临边界点时必输。

根据数学研究，这些边界实际是两条直线：

在二维坐标系上这两条直线的坐标计算方式是

\phi = \frac{1 + \sqrt{5}}{2} \approx 1.6180339887\dots \\ \frac{y}{x} = \phi \\ \frac{x}{y} = \phi

其中 $\phi$ 常被称为“黄金比例”（Golden Ratio），也称“黄金分割”。黄金分割常数是一个无理数，任何正整数乘以或除以它，结果都不是整数。本问题中给定一个坐标时可以算出另一个黄金分割点的坐标，再向坐标系的外围方向取整，可以得到两条直线上安全局势的边界点。我们将二维坐标系上半边黄金分割线称为 $upper$ ，黄金分割线称为 $lower$ 。