威佐夫博弈：两堆石子的黄金必败点

题目

有两堆石子，数量分别为 $(a,b)$（$a\le b$）。两人轮流操作，每步可以：

• 从一堆中取走任意正整数个；或
• 从两堆中同时取走相同数量。

取走最后一枚者胜。哪些局面是**必败（先手必输）**的？

答案与解析

必败局面（记为“冷位置”）是： $( \lfloor k\varphi\rfloor,\ \lfloor k\varphi^2\rfloor ),\quad k=0,1,2,\dots$ 其中 $\varphi=\frac{1+\sqrt5}{2}\approx1.618$ 是黄金比，且 $\varphi^2=\varphi+1$。

前几个必败态： $(0,0),\ (1,2),\ (3,5),\ (4,7),\ (6,10),\ (8,13),\ (9,15),\dots$

检验：从 $(1,2)$ 出发，无论怎么取，都会落到某个非必败态；而每个非必败态，总有一种取法跳进某个必败态。于是必败态互相“钉死”了胜负。

背后的数学

这是 1907 年威佐夫（Wythoff）提出的威佐夫博弈。它神奇地用到了贝亚蒂定理（Beatty’s Theorem）：两序列 $\lfloor k\varphi\rfloor$ 与 $\lfloor k\varphi^2\rfloor$ 恰好不重不漏地覆盖所有正整数——所以每个非必败态都唯一对应一个必败态可一步到达。博弈论与无理数的这场联姻，堪称组合数学里最优雅的巧合之一。