月牙岛上种着一种神奇的月萝卜,只在月光下生长,田心那颗最大的「月心萝卜」攒满了一整个月的月光。传说谁拔到月心萝卜,谁家就一整年亮堂堂。兔王长耳是岛上的庄家,每年月圆节都摆下一田萝卜挑战全村孩子:「拔到我这一根,月光归您;拔不到嘛……哼哼,明年再来!」
规矩很简单:轮到谁,谁就拔至少一根;第一次随便拔(但不能把整田拔光),之后每次最多拔对手上一回的两倍。兔王自认这规矩天衣无缝——直到老龟龟灵博士发现,密码竟藏在「把数拆成不相邻的斐波那契数」里。
这游戏在数学里叫 Fibonacci Nim(斐波那契取子游戏),是经典 NIM 的亲戚——但「不能超过对手两倍」这条限额,让它和普通 NIM 完全两个世界。1963 年,Michael J. Whinihan 在《Fibonacci Quarterly》创刊不久便完整破解了它,破解的钥匙正是 1972 年才被命名的 Zeckendorf 表示。
顺带一提:斐波那契数列 1, 1, 2, 3, 5, 8, 13… 本身就来自 1202 年斐波那契《算盘全书》(Liber Abaci)里那道著名的兔子繁殖问题——用兔子破解兔子游戏,刚刚好。
龟伯发现:每个正整数都能唯一写成若干个互不相邻的斐波那契数之和(Zeckendorf 定理)。其中最小的那个分量就是这堆萝卜的安全线——
Whinihan 定理:轮到您时,限额 ≥ 安全线 ⟹ 您必胜,第一茬就拔「安全线」那么多根;限额 < 安全线 ⟹ 您必败。尤其当剩余数本身是斐波那契数时,整堆就是一个分量、安全线 = 全部——所以首手几乎永远动不得它。
要诀就一条:轮到您时,拔走「安全线」那么多根。留下的数,它的最小分量会变成原来的两倍还多——对手的限额翻倍也够不着,只能眼看着您一根一根收网。
彩蛋(贪心会翻车):剩 20 根、限额 19 时,「拔 7 留 13」看着漂亮——可对手面对 (13, 限额 14) 能整田全拔直接赢您!正解是拔 2 留 18(18 = 13 + 5,安全线 5 > 2×2),对手立刻掉坑。
和所有 NIM 亲戚一样,这里也有一条铁律——任意局面,轮到谁走,要么必胜、要么必败,没有第三种。
低星级时兔王常常打盹拔错——那是练手的好机会;到了月心之巅,他每茬都精确,就看您拆数的功夫啦。
相邻斐波那契数之比 Fk+1/Fk 会越来越靠近 黄金比 φ ≈ 1.618——所以「两倍限额」的取子游戏,密码居然和威索夫棋金格密码(⌊kφ⌋、⌊kφ²⌋)是同一家族。规则里一个小小的「2 倍」,让黄金比在两盘游戏里各自开出一朵花——这就是数学的浪漫。