西尔维钱币

西尔维钱币, 即 Sylver 钱币, 是 John Horton Conway 发明的数学游戏, 其名称来自数学家 James Joseph Sylvester, 亦与英文 silver 谐音. 本条目采用的中文名来自参考文献 Winning Ways for Your Mathematical Plays 的通行中译本《稳操胜券》, 由谈祥柏翻译.

1规则

《稳操胜券》杜撰了如下故事以解释游戏名称:

“… 纽皇帝推翻了分崩离析的米纽斯王朝而取得政权. 这个政权推行了一些积极改革, 特别是废除了旧通货 (上面有旧统治者的头像), 引进新的皇家 (纽氏) 体制. 高先生与矮先生是皇家造币厂的两位厂长, 他们被皇上授予特权, 轮流地来决定每一种新币的币值, 在他们的每个新决定颁布以后, 随即制造出这一币值的大量新币. 以上一切事情都进行得很顺利, 直至有一天, 高先生决定铸造一种币值为 $1$ 的新货币, 而这将使造币厂的工人大量失业. 工人们怒不可遏, 他们揭竿而起, 在京城的一个僻静角落里把不幸的高先生抛下高塔殒命. 由于这一历史典故, 高塔就此出了名.”

米纽斯——四分五裂的年代

换言之, 游戏规则如下:

定义 1.1 (西尔维钱币). 甲乙二人轮流写下大于 $1$ 的整数, 且不能写已有数的自然数系数线性组合. 不能行动者输.

为简明起见, 以后把 “自然数系数线性组合” 称为 “正线性组合”. 此外对集合 $S\subseteq {\mathbb{Z}}_{>1}$, 我们以 “局面 $S$” 表示已经写下的数集为 $S$ 的局面.

例 1.2. 以下是一局游戏:

•	甲写下 $2$.
•	乙写下 $3$.
•	甲输了.

例 1.3. 以下是另一局游戏:

•	甲写下 $5$.
•	乙写下 $4$.
•	甲写下 $11$.
•	乙写下 $6$.
•	甲写下 $7$.
•	乙写下 $2$.
•	甲写下 $3$.
•	乙输了.

2分析

显然, 西尔维钱币是个正常无偏游戏, 故其每个局面都有个确定的 Nim 值. 遗憾的是我们对该游戏知之甚少, 绝大部分局面的 Nim 值尚未求出, 而只知道如下结论:

定理 2.1 (R. L. Hutchings). 设正整数 $a,b$ 大于 $1$、互素、且不是 $2,3$. 则 $\{a,b\}$ 是个 $\mathcal{N}$-局势 (即先手必胜).

证明. 使用盗用策略论证. 由定理 2.4, $a,b$ 的正线性组合不能表示的最大数是 $t=ab-a-b$, 且如 $s$ 不是 $a,b$ 的正线性组合, 则 $t-s$ 一定是. 考察局面 $\{a,b,t\}$. 如它是 $\mathcal{P}$-局势 (即后手必胜), 则 $\{a,b\}$ 局面的先手可以写下 $t$ 从而进入必胜局面. 如它是 $\mathcal{N}$-局势, 设其先手必胜策略第一步为 $s$, 则 $s<t$ 且不是 $a,b$ 的正线性组合. 于是 $t$ 是 $a,b,s$ 的正线性组合, 故局面 $\{a,b,t,s\}$ 与 $\{a,b,s\}$ 没有区别, 从而 $\{a,b\}$ 局面的先手可以写下 $s$ 而进入必胜局面. 所以不论如何 $\{a,b\}$ 局面的先手总有必胜策略.

$\square$

以下显然推论说明初始局面先手必胜. 事实上例 1.3 的甲已经展示了此事.

推论 2.2. 设 $p>3$ 为素数. 则 $\{p\}$ 是个 $\mathcal{P}$-局势 (即后手必胜).

证明. 由定理 2.1, 此时任一操作都会给出 $\mathcal{N}$-局势.

$\square$

推论 2.3. 设正整数 $n$ 为合数且有大于 $3$ 的素因子. 则 $\{n\}$ 是个 $\mathcal{N}$-局势.

证明. 取 $n$ 的大于 $3$ 的素因子 $p$, 则先手写下 $p$ 就会来到 $\mathcal{P}$-局势.

$\square$

以下定理是该游戏以 Sylvester 命名的原因.

定理 2.4 (Sylvester). 设 $a,b$ 是互素自然数. 则 $a,b$ 的正线性组合不能表示的最大数是 $t=ab-a-b$, 且对任意 $s\in \mathbb{Z}$, $s$ 和 $t-s$ 中恰有一个是 $a,b$ 的正线性组合.

证明. 由 Bezout 定理, 任一整数 $x$ 都可写成 $ma+nb$ 的形式, 其中 $m,n\in \mathbb{Z}$. 把 $m$, $n$ 换成 $m+kb$, $n-ka$, 其中 $k\in \mathbb{Z}$, 可不妨设 $0\le m<b$. 此时不难发现 $x$ 是 $a,b$ 的正线性组合当且仅当 $n\ge 0$. 换言之:

•	$a,b$ 的正线性组合能表示整数可以唯一写成 $ma+nb$, 其中 $0\le m<b$, $n\ge 0$.
•	$a,b$ 的正线性组合不能表示的整数可以唯一写成 $ma+nb$, 其中 $0\le m<b$, $n<0$.

由于 $a,b\ge 0$, $ma+nb$ 关于 $m,n$ 单调, 所以 $a,b$ 的正线性组合不能表示的最大数是 $(b-1)a-b=ab-a-b$. 又注意到 $m\mapsto b-1-m$ 是 $\{m\in \mathbb{Z}\mid 0\le m<b\}$ 到自身的双射, $n\mapsto -1-n$ 是 ${\mathbb{Z}}_{\ge 0}$ 到 ${\mathbb{Z}}_{<0}$ 的双射, 由此可知 $s\mapsto t-s$ 是 $a,b$ 的正线性组合可以表示的数与其不能表示的数之间的一一对应, 此即欲证.

$\square$

由于定理 2.1 是通过盗用策略证明的, 它并没有给出显式的必胜策略, 也给不出 Nim 值的信息. 一些枚举和配对可以说明 $\{2,3\}$, $\{4,6\}$, $\{6,9\}$, $\{8,12\}$ 都是 $\mathcal{P}$-局势, 从而 $\{2\}$, $\{3\}$, $\{4\}$, $\{6\}$, $\{8\}$, $\{9\}$, $\{12\}$ 全都是 $\mathcal{N}$-局势, 然而如下问题仍悬而未决:

猜想 2.5. 设正整数 $n$ 的素因子只有 $2$ 和 $3$. 则 $\{n\}$ 是 $\mathcal{N}$-局势.

3参考文献

•	Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (1982). Winning Ways for Your Mathematical Plays, "Chap. 18: The Emperor and His Money".

•	The Sylver Coinage Page

术语翻译

西尔维钱币 • 英文 Sylver coinage