又是一枚康威的硬币——为致敬 Sylvester 而故意拼作 Sylver。双方轮流「铸币」:报出一个不能由已报之数非负组合表出的正整数;谁被迫报出 1,谁就输。 规则一行讲完,棋局却至今未被完全求解:Hutchings 定理保证大素数开局必胜,却不肯透露半步胜着。本站四进:铸币对局、铸币实验室、策略教程、为什么。
被迫报 1 者输。AI 的棋力来自与页面同源的求解引擎:有限局面精确求解(胜方求快、败方求拖); 开放局面(gcd>1)则诉诸已知理论——对 2 报 3 的经典应手,其余尽力顽抗。若您的开局是素数 ≥5, 理论上您已占了 Hutchings 定理的便宜——但胜着得自己找。
「开放」指已报之数的最大公约数 g>1:此时凡非 g 之倍数又未被表出者皆可报,余地无限——这正是 Sylver Coinage 至今未解的根源。 一旦两枚互素之币落桌,半群 ⟨a,b⟩ 补集骤然有限,最大缺口就是 Frobenius 数;二元情形有 Sylvester 公式 (a−1)(b−1)−1 可对照。
表中只列「一手有限化且制胜」的应手(cap≤12):对 2 报 3、对 3 报 2——漂亮的对偶,同归半群 ⟨2,3⟩, 对手被迫铸下毒币 1。其余开局任何互素应手都会让对手拿到含 ender 的 N 局, 故真正的应手是多手缠斗(对 4、6、8、9、12 的完整策略见《Winning Ways》,但非一手之功)。 素数 5、7、11 开局必胜是 Hutchings 定理(策略偷取),但定理不给出应手——空格不是「没有胜着」,而是「无人知晓」。
若按常规「报出最后一数者胜」,则开 1 即胜,游戏退化。Conway 把 1 设为毒药:谁报 1 谁输。 于是 1 永远留在可报之列——像达摩克利斯之剑,逼每个棋手在「封住对手」与「不给自己留绝路」之间走钢丝。
互素的 a、b 无法表出的最大整数为 (a−1)(b−1)−1,且不可表之数恰有 (a−1)(b−1) 个。 证明的钥匙:把 0,…,ab−1 排成 a 行 b 列的表格,数 n 写在 (n mod a, n mod b)——同行者两两可互表, 每行恰有一个缺口,缺口从上到下递增,最深的缺口就是 Frobenius 数。 例如 ⟨4,5⟩:缺口 {1,2,3,6,7,11},最大 11 = 3×4−1,共 12 = 3×4 个。
已报之数的全体非负组合构成数值半群 ⟨gens⟩;合法着恰是它的补集(gap)。 gcd=1 时补集有限(否则无限——游戏还「在大海上」)。求最大 gap 即 Frobenius 铸币问题: 二元有上式闭解,三元起无闭式,变元个数不定时一般判定是 NP-难的。本页面的求解引擎走的是另一条路: 对模最小币的每个剩余类求「最短可表值」(Dijkstra),从而一次列出全部缺口。
有限局面中,若最大的可报数 g* 具有性质「报其他任何合法数都会把 g* 杀掉」(即 g* 落入新半群), 则 g* 称为 ender。此时轮走者可循「ender 策略」取胜:若非 ender 着中有胜着,走之; 若皆非胜着,则走 ender——此后对手任一着法所至的局面,都比原局面少了一枚币, 归纳地可偷取其胜势(⟨2,3⟩ 只剩 {1} 是唯一例外:ender 局面也可面为 P)。 对两枚互素之币 a、b,其 Frobenius 数 (a−1)(b−1)−1 恰为 ender(引擎可逐项验证:F 减去任一缺口皆可表出), 故两枚互素之币落桌后,行棋方几乎必胜——这就是 Hutchings 定理的核心:素数 p≥5 开局, 对手无论应何数,⟨p,x⟩ 的 Frobenius 数都是 ender,先手稳操胜券——但定理不指认胜着。
本站引擎对 5、7 开局后在应手 ≤12 范围内程序验证了「一切应手皆先手 N」——Hutchings 的有界影子; 同时也实证了它的另一面:对 3、4 等开局,任何一手有限化应手都送出 N 局——真正的应手是多手缠斗。
① 是否存在非素数的必胜开局?(连 4 都已知是败着,但 10、14、15……无人完全知晓。) ② 素数开局的显式必胜策略是什么?③ 开放局面(gcd>1)的一般理论几乎整片空白。 一个规则一行讲完的游戏,四十五年来仍向人类讨教。
参考文献:Berlekamp–Conway–Guy《Winning Ways for your Mathematical Plays》(1982) Sylver Coinage 一节; J. J. Sylvester, Educational Times, Q7382 (1884);Wikipedia "Sylver coinage";AMS Feature Column "What is a combinatorial game?"。