大老李聊数学和天南海北

十步万度与沙堆群

大老李 · 先玩游戏 · 群论演示

前言

有这么一个名为“十步万度”的小游戏。游戏中有一个 5×5 的表盘阵列，每个表盘中有一个指针，初始全部向上。

当你点击任何一个表盘时，其会顺时针转动90度。转动后，如果指针指向另一个表盘，则那个表盘也会顺时针转动90度，如此连锁反应一直持续下去，直到指针指向外围区域。

游戏的目标是在10次点击内，使得表盘总的旋转度数达到一万度，故名“十步万度”。我让AI做了一个在线版，你可以先玩玩看。

这个游戏难度挺大，要达成十步万度并不容易。但在游戏过程中，你很快能发现游戏中的一个奇妙性质：游戏的得分与点击次序无关！一个更强的结论是：如果初始局面相同，给定一个点击组合，比如$(a_1,a_2,a_3,\cdots, a_{25})$，其中$a_i$是对第i个表盘的点击次数，那么无论点击次序如何，完成点击后每个表盘转过的度数都相等，最终局面自然也相同。

那么如何证明以上结论？相信你会想到交换群的概念。如果能把游戏抽象为某个群，并且证明其具有交换性，也就是阿贝尔群，那么也就证明了点击次序不影响游戏结果这一性质。直觉上这个群的元素是点击的位置，但是点击产生的效果显然是与局面状态有关的。所以仅仅25个元素，无法描述游戏的过程。那么似乎可以把点击组合作为群的元素，但每个位置可以点击任意多次，所以点击组合有无穷多种，这样会导致群有无穷个元素，似乎有点把问题复杂化了。所以问题的关键变为，如何“合并”点击组合，使得最终能得到一个有限群？

我搜索了一番，发现数学家已经研究过两种群模型：沙堆群（Sandpile Group）和转子路由群（Rotor-Router Group），后者可以理解为前者的一种特例，而转子路由群可以完美地应用在十步万度游戏中。下文我将介绍这两个群的概念，以及如何用群论分析十步万度游戏。你将发现，十步万度对应的转子路由群有多达 $32{,}565{,}539{,}635{,}200$ 个元素。尽管元素这么多，它的各种性质仍在可计算范围内。

一旦将游戏抽象为群，很多与游戏相关的问题都可以回答。除了前述的交换性质，还有：是否所有状态互相可达？连续点击某个位置是否可以使局面还原？是否有一个点击组合使得局面不变？对每一个组合，是否有另一个组合可以抵消它的操作（还原到点击前的状态）？

以上这些问题，一旦把游戏抽象为群，都会迎刃而解。

以下科普内容主要参考 6 位研究者在 2008 年发表的论文：《Chip-Firing and Rotor-Routing on Directed Graphs》，下文提到的“论文”都指这篇论文。

下文的前半部分会介绍沙堆群和转子路由群的定义和一些性质。为方便对照，文中提到的引理和定理编号与论文中的相同。具体证明过程一般从略，若有兴趣，可以直接阅读上述论文。后半部分会使用转子路由群对十步万度游戏进行分析，回答一些游戏中的有趣问题。

文章非常长，其中不可避免地用到了大量AI生成文字，不喜勿喷。这些AI生成内容是非常有营养的，请耐心看完，一定会有收获。

沙堆群

我们来定义一个“筹码发射”（Chip-Firing）游戏，这个游戏是在图论中的“图”（Graph）上玩的，以下简单介绍一些会用到的图论概念。

图：一些点和边构成的集合。

有向图：边是有方向的。

出度：从某点出发的边的数量。

入度：到达某点的边的数量。

汇点（sink）：出度为0的点。

全局汇点（global sink）：是汇点，且从其他任何点出发，均可沿边的方向抵达该点。本文中，我们要求全局汇点是唯一的。

双向图（bidirected）：若 A、B 相邻，则 A 到 B 和 B 到 A 的边各有一条。本文中，如果一个图中去掉全局汇点后，剩下的图是双向图，我们称这个图是具有全局汇点的双向图。

alt text

上图是一个具有全局汇点的双向图的例子，其中d是全局汇点。

邻接矩阵（Adjacency matrix）：图的一种常用矩阵表示方法。其定义是：$n\times n$的矩阵，且$(i,j)$位置的值为从$v_i$点到$v_j$点的边的数量。

拉普拉斯矩阵（Laplacian matrix）：也叫调和矩阵。是除邻接矩阵外，另一种常用的图的矩阵表示。其定义是：

如果图有n个点，其邻接矩阵是A，D是出度对角矩阵，即每个点的出度放在对角线上，则其拉普拉斯矩阵$\Delta$的定义是:

$$\Delta = D - A$$

例如，之前的例子中，各点出度：a 为 2，b 为 2，c 为 2，d 为 0。

可达性：a 和 c 直接指向 d，b 经 a 或 c 到 d，所以d是全局汇点。

从上到下每一行分别表示a、b、c、d四个点，则A、D、$\Delta$分别是这个图的邻接矩阵，出度对角矩阵和拉普拉斯矩阵：

$$ A=\begin{pmatrix} 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 \end{pmatrix}, \qquad \qquad D=\begin{pmatrix} 2 & 0 & 0 & 0\\ 0 & 2 & 0 & 0\\ 0 & 0 & 2 & 0\\ 0 & 0 & 0 & 0 \end{pmatrix}, $$
$$ \Delta=D-A=\begin{pmatrix} 2 & -1 & 0 & -1\\ -1 & 2 & -1 & 0\\ 0 & -1 & 2 & -1\\ 0 & 0 & 0 & 0 \end{pmatrix}. $$

拉普拉斯矩阵的一个显著特点是每一行的数字之和为0，因为对角位置和其他位置的数字正好抵消。如果我们去掉全局汇点所在的行和列，所得矩阵被称为“约化拉普拉斯矩阵”，通常用$\Delta^\prime$表示：

$$ \Delta'=\begin{pmatrix} 2 & -1 & 0\\ -1 & 2 & -1\\ 0 & -1 & 2 \end{pmatrix}, $$

这个约化拉普拉斯矩阵在后面会很有用。

接下来定义一个双向图上的筹码发射游戏。首先想象双向图的每个点上有一定数量的筹码，这样的状态称为一个“筹码配置”（chip configuration）。比如下图表示一个 3 个点的双向图，其中一个点上有 3 个筹码，其他两个点没有筹码：

当图中所有非汇点上的筹码数量都小于其出度时，称这个筹码配置是“稳定”（stable）的，否则就是不稳定的，或“活跃”（active）的。

定义一种“发射”操作：

对不稳定的筹码配置，任意选择一个筹码数量不小于其出度的点，沿它的每条出边各“发射”一枚筹码到所指向的点。换句话说，如果这个点的出度是 n，那么这个点上的筹码减少 n，而其出边所指向的每个点各增加 1 枚筹码。以下是两种不同筹码配置的发射过程：

可以看到第一种筹码配置下，1次发射后，就进入稳定状态。第二种配置下，无论如何发射，都不会进入稳定状态。看到这种情况，相信你很快会产生一系列疑问：

问题1: 什么样的配置可以进入稳定状态？有没有判定方法？

确实有一些稳定性的判定方法，但对本文有用的判定条件只有一个：

引理2.4: 如果双向图G有全局汇点，则G上所有筹码配置都会进入稳定状态。

具体证明不再赘述，不过可以想象，如果有全局汇点，筹码总会不断流入汇点而越来越少，直到进入稳定状态。

问题2: 如果有全局汇点，且同时有多个可发射的位置，改变发射顺序会影响最终稳定时的筹码配置吗？

答案你或许也猜到了：不会！无论怎么发射，最终都进入同一种稳定的筹码配置。事实上有更强的结论：

定义“添加筹码”操作：在图G的某个点上添加一个筹码，然后发射，直到进入稳定状态。

引理2.5: 添加筹码操作是可交换的。

推论2.6: 对有全局汇点的双向图，只要对每个点添加相同数量的筹码，无论添加次序如何，发射后都进入同一种稳定状态。

在群论中，“阿贝尔”是可交换的代名词，所以以上这种性质被称为“阿贝尔性质”（abelian property）。

问题3: 有全局汇点的双向图，可以有几种稳定状态？

显然可以有多种稳定状态，所以我们希望有一个工具来刻画稳定状态的数量和结构。幸而数学家发现，这些稳定状态构成了一个群！这个群的定义是一个商群形式：

$S(G)=Z^{n-1}/Z^{n-1}\Delta ^\prime (G)$

$S(G)$ 被称为图 G 的沙堆群（Sandpile Group）。n 为图 G 中点的数量，n-1 就是非汇点的数量。

商群的“分子”是一个群，这里的 $Z^{n-1}$ 就是 n-1 维整数向量构成的群，其中的群元素是由 n-1 个整数构成的行向量：

$(a_1, a_2, \cdots, a_{n-1})$，群运算是向量逐分量相加，单位元是零向量。

商群的“分母”是“分子”的正规子群，这里的分母是 $Z^{n-1}\Delta ^\prime (G)$，其中 $\Delta ^\prime$ 是 G 的约化拉普拉斯矩阵。这个正规子群的元素，就是 $\Delta ^\prime$ 各行的所有整系数线性组合。

以上这个定义挺抽象，所以我们需要理解这个定义的含义。学过群论的读者知道，商群的一个直观理解就是对“母群”（分子上的那个群）进行了某种“合并同类项”。那么沙堆群到底进行了怎样的合并？合并后的群有几个元素呢？

关于沙堆群的元素个数，论文引理 2.8 证明了它恰为 $\Delta ^\prime$ 的行列式（determinant）的值。对之前的例子，

$$ \Delta'=\begin{pmatrix} 2 & -1 & 0\\ -1 & 2 & -1\\ 0 & -1 & 2 \end{pmatrix}, $$

其行列式$\text{det} \Delta^\prime =4$，所以其对应的沙堆群只有4个元素，我们可以在这个沙堆群上做一次详细的运算演示，直观了解这个沙堆群的含义。

沙堆群的运算演示

alt text

上图中：非汇点 $a,b,c$，全局汇点 $d$；边为 $a\leftrightarrow b$，$b\leftrightarrow c$，$a\to d$，$c\to d$。三个非汇点出度都是 2。按 $a,b,c$ 顺序，

$$ \Delta'=\begin{pmatrix} 2&-1&0\\-1&2&-1\\0&-1&2\end{pmatrix},\qquad \det\Delta'=4, $$

所以沙堆群有 4 个元素，是循环群 $\mathbb{Z}_4$。

发射规则。 筹码配置记作 $(s_a,s_b,s_c)$。某点筹码数 $\ge 2$ 时可以发射：$a$ 发射送 1 枚给 $b$、1 枚给 $d$；$b$ 发射送 1 枚给 $a$、1 枚给 $c$；$c$ 发射送 1 枚给 $b$、1 枚给 $d$。送到 $d$ 的筹码消失。

群元素。 稳定配置是每点 0 或 1，共 8 个；其中常返（后面会说明“常返”的含义）的只有 4 个，它们就是群元素：

配置 $(s_a,s_b,s_c)$ 阶 说明
$(1,0,1)$ 1 单位元 $I$
$(1,1,1)$ 2
$(0,1,1)$ 4 生成元，记作 $g$
$(1,1,0)$ 4 $g^3=g^{-1}$

另外 4 个稳定配置 $(0,0,0),(1,0,0),(0,1,0),(0,0,1)$ 不是常返的，不属于群。

群运算。 两个配置逐点相加，然后反复发射直到稳定，记作 $(\sigma+\sigma')^\circ$。下面用 $g=(0,1,1)$ 的幂次把整个群走一遍，箭头上标出发射的点：

$g^2=(g+g)^\circ$：

$$ (0,2,2)\xrightarrow{b}(1,0,3)\xrightarrow{c}(1,1,1). $$

$g^3=(g^2+g)^\circ$：

$$ (1,2,2)\xrightarrow{b}(2,0,3)\xrightarrow{a}(0,1,3)\xrightarrow{c}(0,2,1)\xrightarrow{b}(1,0,2)\xrightarrow{c}(1,1,0). $$

$g^4=(g^3+g)^\circ$：

$$ (1,2,1)\xrightarrow{b}(2,0,2)\xrightarrow{a}(0,1,2)\xrightarrow{c}(0,2,0)\xrightarrow{b}(1,0,1)=I. $$

四次回到单位元，所以 $g$ 的阶是 4，群是 $\mathbb{Z}_4=\{I,g,g^2,g^3\}$。

再看几条验证。

  • 单位元确实不改变任何元素：$I+g=(1,1,2)\xrightarrow{c}(1,2,0)\xrightarrow{b}(2,0,1)\xrightarrow{a}(0,1,1)=g$。
  • 阶 2 元素自乘回到单位元：$(1,1,1)+(1,1,1)=(2,2,2)$，依次发射 $a,b,c,b,a,c,b$ 共 7 次后得 $(1,0,1)=I$。
  • 互逆元素相乘：$g+g^3=(0,1,1)+(1,1,0)=(1,2,1)$，稳定化后为 $(1,0,1)=I$，与 $g^4$ 的计算完全一样。

用矩阵理解。 $\Delta'$ 的三行是 $r_a=(2,-1,0)$，$r_b=(-1,2,-1)$，$r_c=(0,-1,2)$。发射一次 $v$ 就是减去 $r_v$。上面 $g^4$ 的计算共发射了 $a$ 一次、$b$ 两次、$c$ 一次，于是

$$ (1,2,1)-(1,0,1)=(0,2,0)=r_a+2r_b+r_c , $$

即 $g^4$ 对应的向量 $4g=(0,4,4)$ 与 $I=(1,0,1)$ 相差一个行格中的向量，二者在商群 $\mathbb{Z}^3/\mathbb{Z}^3\Delta'$ 中是同一个元素。这就是"常返配置上的加法加稳定化"与"整数向量模 $\Delta'$ 行格"两种定义之间的对应。

相信你看完以上说明之后，一定有豁然开朗之感！沙堆群的定义，直观说明就是：

沙堆群的元素是筹码配置的等价类，两个筹码配置属于同一个等价类，当且仅当从两个配置出发，发射后进入同一种稳定状态。群运算是把两个配置叠加后发射到稳定，叠加就是在一个配置的每个位置上加上另一个配置对应位置的筹码数。

这里再说明一下“常返”的定义：从之前的演示中可以看到，该图有 8 种稳定配置，但有 4 种比较特殊，只有从特殊的初始条件出发才能到达。比如 (0,0,0) 这种稳定配置：如果一开始筹码很多，那么无论如何增加筹码和发射，都不可能让筹码全部消失。

如果从任何配置出发，都可以通过增加筹码和发射操作到达某个配置，就称这个配置是“可达”（accessible）的。可达的稳定配置被称为“常返”（recurrent）的。论文作者证明了，沙堆群的每个元素，也就是每个配置等价类中，恰好有一个常返稳定配置，所以通常用这些常返稳定配置作为沙堆群元素的代表元。而我之前说，“沙堆群的每个元素对应了一种稳定配置”，应该改为“沙堆群的每个元素对应了一种 常返稳定配置”，才是准确说法。

有了沙堆群，我们可以解一些关于筹码发射游戏的有意思的应用题。比如下面是 AI 给的一个例子：

问：用沙堆群能否快速计算某个配置最终的稳定状态？比如 $(100,50,25)$，不逐步模拟发射，如何知道它属于哪个等价类？

可以。沙堆群正是为此而设的：等价类由线性代数一步算出，不需要逐次发射。分三步说。

第一步：找一个"类函数"。 沙堆群是 $\mathbb{Z}^3/\mathbb{Z}^3\Delta'$，对这个图它同构于 $\mathbb{Z}_4$，所以存在一个同态 $\varphi:\mathbb{Z}^3\to\mathbb{Z}_4$，其核恰好是 $\Delta'$ 的行格。写 $\varphi(\sigma)=w\cdot\sigma \bmod 4$，要求 $w$ 与 $\Delta'$ 的每一行点积都是 4 的倍数：

$$ r_a=(2,-1,0),\ r_b=(-1,2,-1),\ r_c=(0,-1,2) \;\Longrightarrow\; 2w_a-w_b\equiv 0,\quad -w_a+2w_b-w_c\equiv 0,\quad -w_b+2w_c\equiv 0 \pmod 4 . $$

解得 $w=(1,2,3)$，于是

$$ \varphi(s_a,s_b,s_c)=s_a+2s_b+3s_c \pmod 4 . $$

用四个常返配置核对：$I=(1,0,1)\mapsto 0$，$g=(0,1,1)\mapsto 1$，$g^2=(1,1,1)\mapsto 2$，$g^3=(1,1,0)\mapsto 3$。$\varphi$ 把每个配置直接送到它在 $\mathbb{Z}_4$ 中的元素。

第二步：对 $(100,50,25)$ 求类。

$$ \varphi(100,50,25)=100+100+75=275\equiv 3 \pmod 4 , $$

所以它属于 $g^3$ 的等价类，这一类里唯一的常返配置是 $(1,1,0)$。

还要确认稳定化的结果就是这个常返配置，而不是同类中某个非常返的稳定配置。判据很简单：$(100,50,25)\ge I=(1,0,1)$ 逐点成立，即它是"单位元加上若干筹码"，而在常返配置上加筹码再稳定化仍是常返的。所以最终稳定配置就是 $(1,1,0)$。模拟验证一致，共发射 284 次。

第三步：连发射次数也能直接算。 设 $x_v$ 是 $v$ 的发射次数，则 $\sigma-\sigma^\circ=x\Delta'$，因此

$$ x=(\sigma-\sigma^\circ)\,\Delta'^{-1},\qquad \Delta'^{-1}=\frac14\begin{pmatrix}3&2&1\\2&4&2\\1&2&3\end{pmatrix}. $$

代入 $\sigma-\sigma^\circ=(99,49,25)$ 得 $x=(105,111,68)$，总计 284 次，与模拟完全相同。流入汇点的筹码数是 $x_a+x_c=173=175-2$，也对得上。

一个必要的提醒。 $\varphi$ 给出的是等价类，稳定化结果 $\sigma^\circ$ 只有在 $\sigma$ 逐点不小于某个常返配置时才等于该类的常返代表。例如 $(0,0,0)$ 的类是 0，代表元是 $I=(1,0,1)$，但它本身已经稳定，$\sigma^\circ=(0,0,0)$。筹码总数很少时才会出现这种情况；像 $(100,50,25)$ 这样的大配置不会。

沙堆模型起源于1987年，由 Per Bak、汤超（1958 - ，现为西湖大学和北京大学讲席教授）和 Kurt Wiesenfeld在一篇研究自组织临界性（self-organized criticality）动力系统的论文中提出，此后Deepak Dhar发现沙堆模型具有可交换性，提出了沙堆群概念。

沙堆模型的一个特点是在大尺度下，会呈现一些“自发”形成的组织结构。比如考察很大的正方形“沙堆”，即双向图为正方形网格，所有边界点连接到一个全局汇点，其单位元的样子如下：

其中左上为 128×128，右上为 198×198，左下为 243×243，右下为 521×521。不同颜色对应不同的数字，橙色=0，红色=1，绿色=2，蓝色=3。可以看到图像呈现某种颇具神秘感的组织结构。

如果在一个无限网格的原点一次性撒入 3 千万粒沙子，按照筹码发射规则发射到稳定，最终会呈现下面的图像（白色 0 粒、绿色 1 粒、紫色 2 粒、金色 3 粒）：

alt text

转子路由群

看过沙堆群的介绍，相信你能感觉到它与十步万度游戏有某种相似性，但又无法直接关联起来，所以我们再引入一个“转子路由群”（rotor-routing group）的概念。论文中，作者把它定义为作用在以全局汇点为根的所有生成树上的一个置换群。以下直接用十步万度游戏为例：

把游戏看成有向图 $G$：顶点是 25 个格子加一个汇点 $s$；每个格子有 4 条出边，分别指向上、右、下、左的邻格，出界的边指向 $s$。于是每个格子的出度 $d_v=4$，出边的循环顺序是上→右→下→左。所有格子都能到达 $s$，即 $s$ 是全局汇点。

定义加筹码算子 $E_v$：在 $v$ 放一枚筹码并按转子规则一路走到汇点，得到的转子配置变换。这正是「点击 $v$」。论文 Lemma 3.9（阿贝尔性质）断言 $E_vE_w=E_wE_v$。

令 $\mathcal T$ 为以汇点为根的所有有向生成树的集合，$\mathrm{Sym}(\mathcal T)$ 为 $\mathcal T$ 上所有置换（permutation）构成的群，那么转子路由群就是 $\mathrm{Sym}(\mathcal T)$ 中由各 $E_v$ 生成的子群。

这个定义有点抽象，但引理3.19证明了，转子路由群同构于沙堆群。对十步万度游戏来说，其转子路由群同构于$S(G)=\mathbb{Z}^{25}/\mathbb{Z}^{25}\Delta'$。那么如何理解这个群中的元素和运算与游戏的关系？AI提供了三种理解方式：

描述一：点击计数向量模「4 换 4 邻」关系

  • 元素：一个整数向量 $\sigma\in\mathbb{Z}^{25}$，给每格记一个整数，表示这格被点击的净次数，负数表示撤销点击。两个向量视为同一个群元素，当且仅当它们的差是 $\Delta'$ 各行的整系数组合。$\Delta'$ 在 $v$ 的那一行是：$v$ 处 $+4$，$v$ 的每个网格内邻居处 $-1$。所以生成关系只有一条：在 $v$ 点 4 次 $\sim$ 在 $v$ 的每个网格内邻居各点 1 次（边角格的邻居少，对应的筹码直接出界丢掉）。
  • 运算：向量逐格相加，即「把两组点击都做一遍」。
  • 单位元：零向量，什么都不点；任何与零等价的向量也是单位元，例如「中心点 104 次」或那张 52 次点击的表 $I$。
  • 逆元：$-\sigma$，即把每次点击撤销。要用正的点击实现它，就利用阶数：中心点 1 次的逆元是中心再点 103 次。

这是最接近游戏操作的一种理解：25 个格子的点击次数组合构成群的元素；两种点击组合如果总是使游戏从同一状态进入同一状态，就视为同一个元素。

描述二：常返筹码配置，配上「相加再倒塌」

这是论文 Corollary 2.16 的说法。每格放 0 到 3 枚筹码的图称为稳定配置；某格达到 4 枚就「倒塌」，向 4 个方向各送一枚，出界的消失。每个群元素在稳定配置中有唯一一个常返代表，单位元的代表就是矩阵 $I$：

$$ I=\begin{pmatrix} 2&3&2&3&2\\ 3&2&1&2&3\\ 2&1&0&1&2\\ 3&2&1&2&3\\ 2&3&2&3&2 \end{pmatrix} $$

运算是：把两张筹码图逐格相加，然后反复倒塌直到稳定。例如「中心点 1 次」这个元素的常返代表是 $I$ 把中心的 0 改成 1，因为 $I+\mathbf 1_{(2,2)}$ 已经稳定。

这种理解是借用沙堆群的概念，每格上有四枚筹码就发射，群元素是可能的最终稳定状态。

描述三：箭头图本身

这是对本游戏最直观的一种，因为游戏有一个天然的基点：初始的全朝上图 $\rho_0$。由沙堆群在生成树上作用的自由传递性（Lemma 3.13、3.17），$\sigma\mapsto\sigma(\rho_0)$ 是 $S(G)$ 到全部生成树箭头图的双射，所以可以直接说：

  • 元素：游戏中可能出现的每一幅箭头图，共 $\det\Delta'=32{,}565{,}539{,}635{,}200$ 幅。
  • 单位元：全朝上。
  • 运算：设 $\rho_1$ 由点击多重集 $\sigma_1$ 从全朝上得到，则 $\rho_1 * \rho_2 := \sigma_1(\rho_2)$，即「把产生 $\rho_1$ 的那组点击施加到 $\rho_2$ 上」。由 Lemma 3.12 这不依赖 $\sigma_1$ 的选取，由交换性 $\rho_1*\rho_2=\rho_2*\rho_1$。
  • 逆元：把某幅图变回全朝上所需的那组点击对应的图。

举一个最小的例子。从全朝上点中心一次，连锁是中心转向右、(2,3) 转向右、(2,4) 转向右后出界，得到的图 $\rho_c$ 是第 2 行后三格朝右、其余朝上。这幅图就是群元素 $E_{(2,2)}$。它自己连乘 4 次 $\rho_c^{4}$ 等于「四个邻居各点一次」对应的图，连乘 104 次回到全朝上。而 $\rho_c$ 与「角 (0,0) 点一次」的图相乘，就是两处各点一次后的图，先点哪个都一样。

三者的关系

描述三里的运算不是能在图上「看出来」的局部操作，它的定义要经过点击。这正是转子路由群与沙堆群同构（Lemma 3.19）的内容：箭头图上的运算和筹码图上的「加法加倒塌」是同一个群的两种坐标，而描述一是它们共同的「代数底层」。

元素 运算 单位元
描述一 点击计数向量 $\sigma\in\mathbb{Z}^{25}$，模 $\Delta'$ 的行 向量相加 零向量（或 $I$、中心 104 次）
描述二 常返筹码配置 逐格相加后倒塌 矩阵 $I$
描述三 箭头图（有根生成树） 把产生 $\rho_1$ 的点击施加到 $\rho_2$ 全朝上

游戏中的问题和解答

看了以上介绍，相信你对筹码发射和转子路由两个模型都有所了解。以下再回答一些与十步万度游戏直接相关的问题，便于你加深理解。

可交换性

之前介绍了沙堆群和转子路由群具有可交换性，但没有给出具体证明。以下给出一个针对十步万度游戏的、关于点击顺序可交换的证明。主要由 AI 完成，笔者略加注释。

「十步万度」的次序无关性证明

本文证明「十步万度」游戏的一个性质：对同一组点击（多重集），无论以何种次序执行，最终的总度数都相同。 事实上还有更强的结论：每个格子各自的旋转次数、以及最终的箭头状态，都与点击次序无关。

这个性质是数学上转子路由（rotor-router）模型的阿贝尔性质。

一、游戏规则的数学模型

游戏规则：

  • 5×5 网格，每格一个箭头，方向为上、右、下、左之一，初始全部朝上。
  • 点击一格，箭头顺时针旋转 90°。
  • 旋转后若箭头指向网格内的另一格，该格也旋转 90°，如此传递；某次旋转后箭头指向网格外时连锁停止。
  • 每旋转一次累计 90°，共 10 次点击。

形式化如下。

  • 格点集 $V$ 为 25 个格子，另加一个「外部」顶点 $s$（网格之外）。
  • 每格 $v$ 有转子状态 $\rho(v)\in\mathbb{Z}_4$，其中 $0,1,2,3$ 依次对应上、右、下、左。
  • 邻居函数 $N(v,k)$：从 $v$ 沿方向 $k$ 走一步到达的格子，若出界则记为 $s$。

一次点击 $v$ 等价于一枚「筹码」从 $v$ 出发做如下行走：

筹码在格 $x$（$x\ne s$）时：$\rho(x)\leftarrow\rho(x)+1$，旋转计数加 1，筹码移到 $N(x,\rho(x))$。到达 $s$ 时停止。

总度数 $=90\times$ 总旋转次数。由于每次旋转至多把一个格子加入队列，一次连锁反应确实是一枚筹码走出的一条路径。

命题。 固定一个点击多重集 $\{c_1,\dots,c_n\}$（游戏中 $n=10$，同一格可重复点击）。无论以何种顺序执行这 $n$ 次点击，总旋转次数相同；更强地，每个格子的旋转次数相同，最终箭头状态也相同。

二、引理：每次连锁反应必定终止

引理 1. 从任意格出发的连锁反应在有限步内结束。

证明。 反设某枚筹码永不出界。格子有限，故某格 $x$ 被访问无穷多次。每次访问使 $x$ 旋转 90°，所以 $x$ 在四个方向上各把筹码送出无穷多次，因而 $x$ 在网格内的每个邻居也被访问无穷多次。网格连通，归纳可知所有格子都被访问无穷多次，包括边界格。边界格至少有一个方向指向 $s$，它被访问无穷多次就必然某次把筹码送出网格，矛盾。$\square$

三、里程计与「最小作用原理」

多筹码系统

把 $n$ 枚筹码一开始就同时放在 $c_1,\dots,c_n$ 上（多重集）。

  • 合法步：选一个有筹码的格 $x$，对其中一枚筹码执行上面的一步（旋转 $x$、移动筹码）。
  • 合法运行：一列合法步。
  • 完整运行：所有筹码都到达 $s$ 的合法运行。

按顺序 $\sigma$ 玩游戏（先点 $c_{\sigma(1)}$ 让它连锁到底，再点 $c_{\sigma(2)}$，以此类推）就是一个特定的完整运行：每一步只需要当前格的转子状态，其余筹码原地不动；由引理 1 它确实是完整的。因此只需证明所有完整运行的每格步数相同。

预定指令

关键观察：格 $v$ 第 $k$ 次被旋转时，它必然把筹码送向方向 $\rho_0(v)+k \pmod 4$。这与是哪枚筹码、何时发生完全无关。于是每格有一条预先写好的指令序列。定义

  • 里程计：一个合法运行进行到某一时刻时，把每个格子到此刻为止已被旋转的次数记下来，得到一个函数 $V\to\mathbb{N}$，称为该运行在该时刻的里程计。每执行一步（在格 $x$ 旋转一次），里程计只有 $x$ 处的值加 1。下文用 $u(x)$ 表示参照运行结束时的里程计，用 $w(x)$ 表示被比较的运行在中途某时刻的里程计；
  • $a(x)$：初始放在 $x$ 上的筹码数；
  • $T_{y\to x}(k)$：格 $y$ 的前 $k$ 条指令中指向 $x$ 的条数。$T_{y\to x}$ 关于 $k$ 单调不减。

在任意时刻，格 $x$ 上的筹码数只依赖于里程计：

$$ \chi(x)\;=\;a(x)+\sum_{y}T_{y\to x}\bigl(u(y)\bigr)-u(x). \tag{1} $$

其中 $y$ 取遍所有格子。由于只有 $x$ 的四个（边界格更少）网格内邻居才可能有指向 $x$ 的指令，非邻居的 $T_{y\to x}(k)$ 恒为 0，所以求和实际上只对 $x$ 的邻居进行。进入 $x$ 的筹码数由各邻居送出的指令决定，离开 $x$ 的筹码数正是 $x$ 的旋转次数。

主引理

引理 2. 设某完整运行 $R$ 结束时的里程计为 $u$。任取另一个合法运行 $R'$（可以是部分的、尚未结束的），并任取它进行过程中的一个时刻，记此刻 $R'$ 的里程计为 $w$，即 $w(x)$ 是 $R'$ 到此刻为止格 $x$ 已被旋转的次数。则 $w\le u$，即对每个格 $x$ 都有 $w(x)\le u(x)$。

注意 $R'$ 与 $R$ 是两个不同的运行，例如两种不同的点击次序，二者的中间过程互不相关。若 $R'=R$，引理只是「一局中途的计数不超过结束时的计数」这一平凡事实；引理的实质内容在于：另一局 $R'$ 无论怎样进行，其任一时刻的旋转计数都被 $R$ 的最终结果逐格封顶。能把两局放在一起比较，依赖的正是「预定指令」：每格第 $k$ 次旋转送出的方向与哪一局、哪枚筹码无关，所以两局共用同一组 $T_{y\to x}$，公式 (1) 对二者同时成立。

下面把 (1) 中用里程计 $w$ 算出的 $x$ 处筹码数记为 $\chi_w(x)$，它就是此刻 $R'$ 中格 $x$ 上实际的筹码数。

证明。 对 $R'$ 已执行的步数归纳。开始时尚未执行任何步，$w=0\le u$。设某时刻 $w\le u$，$R'$ 的下一步在格 $x$ 执行，故 $x$ 上有筹码，$\chi_w(x)\ge 1$。执行这一步后里程计只有 $x$ 处变为 $w(x)+1$，所以只需证 $w(x)+1\le u(x)$。

对 $R$ 的终态用 (1)：所有筹码都在 $s$，故

$$ 0=a(x)+\sum_y T_{y\to x}(u(y))-u(x) \;\Longrightarrow\; u(x)=a(x)+\sum_y T_{y\to x}(u(y)). $$

对当前运行用 (1)，并利用 $w(y)\le u(y)$ 与 $T$ 的单调性：

$$ w(x)=a(x)+\sum_y T_{y\to x}(w(y))-\chi_w(x) \;\le\; a(x)+\sum_y T_{y\to x}(u(y))-1 \;=\;u(x)-1 . $$

于是执行这一步后 $x$ 的里程计 $w(x)+1\le u(x)$，其余格不变，归纳成立。$\square$

定理

定理. 任意两个完整运行 $R,R'$ 的最终里程计相等：$u=u'$。

证明。 对 $R'$ 应用引理 2（以 $R$ 为参照）得 $u'\le u$；交换角色得 $u\le u'$。$\square$

推论. 引理 2 还说明任何合法运行的总步数都不超过 $\sum_x u(x)$，所以任何执行方式都会终止，且总步数相同。

四、回到游戏

对同一个点击多重集，不同的点击顺序对应不同的完整运行。由定理，它们有相同的里程计 $u$，因此：

  • 总度数 $=90\sum_x u(x)$，与次序无关；
  • 每个格子各自的旋转次数与次序无关；
  • 最终箭头状态 $\rho_0(x)+u(x)\pmod 4$ 与次序无关。

这就是要证的性质。证明中没有用到 5×5 的具体尺寸，也没有用到「初始全部朝上」的条件，所以结论对任何网格尺寸、任何初始箭头状态都成立。

五、说明

这个证明用的是证明 $x=y$ 的经典方法：先证 $x\ge y$，再证 $x\le y$。这里的 x 和 y 是同一种点击组合在两种点击次序下产生的总旋转次数。

证明 $x\ge y$ 的方法是：用 y 次序点击时，每一格的旋转次数都不多于用 x 次序点击时。交换 x、y 亦然，于是 x=y。

沙堆群 / 转子路由群的子群在游戏中的含义

十步万度游戏对应的约化拉普拉斯矩阵 $\Delta^\prime$ 如下，最左列为格子坐标，最右列“行和”是该行各数之和，它等于该格通向外围的边数，内部格子的行和总是 0：

        1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25   行和
(0,0)   4 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0     2
(0,1)  -1  4 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0     1
(0,2)   0 -1  4 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0     1
(0,3)   0  0 -1  4 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0     1
(0,4)   0  0  0 -1  4  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0     2

(1,0)  -1  0  0  0  0  4 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0     1
(1,1)   0 -1  0  0  0 -1  4 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0  0     0
(1,2)   0  0 -1  0  0  0 -1  4 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0  0     0
(1,3)   0  0  0 -1  0  0  0 -1  4 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0  0  0     0
(1,4)   0  0  0  0 -1  0  0  0 -1  4  0  0  0  0 -1  0  0  0  0  0  0  0  0  0  0     1

(2,0)   0  0  0  0  0 -1  0  0  0  0  4 -1  0  0  0 -1  0  0  0  0  0  0  0  0  0     1
(2,1)   0  0  0  0  0  0 -1  0  0  0 -1  4 -1  0  0  0 -1  0  0  0  0  0  0  0  0     0
(2,2)   0  0  0  0  0  0  0 -1  0  0  0 -1  4 -1  0  0  0 -1  0  0  0  0  0  0  0     0
(2,3)   0  0  0  0  0  0  0  0 -1  0  0  0 -1  4 -1  0  0  0 -1  0  0  0  0  0  0     0
(2,4)   0  0  0  0  0  0  0  0  0 -1  0  0  0 -1  4  0  0  0  0 -1  0  0  0  0  0     1

(3,0)   0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  4 -1  0  0  0 -1  0  0  0  0     1
(3,1)   0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0 -1  4 -1  0  0  0 -1  0  0  0     0
(3,2)   0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0 -1  4 -1  0  0  0 -1  0  0     0
(3,3)   0  0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0 -1  4 -1  0  0  0 -1  0     0
(3,4)   0  0  0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0 -1  4  0  0  0  0 -1     1

(4,0)   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0  0  4 -1  0  0  0     2
(4,1)   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0 -1  4 -1  0  0     1
(4,2)   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0 -1  4 -1  0     1
(4,3)   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0 -1  4 -1     1
(4,4)   0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0 -1  0  0  0 -1  4     2

记 5×5「十步万度」的沙堆群为 $S(G)=\mathbb{Z}^{25}/\mathbb{Z}^{25}\Delta'\cong\mathbb{Z}_4\oplus\mathbb{Z}_{16}\oplus\mathbb{Z}_{48}\oplus\mathbb{Z}_{102960}^2$，阶为 $32{,}565{,}539{,}635{,}200$。由自由传递性，它的元素与游戏中全部箭头图（以汇点为根的生成树）一一对应，基点是全朝上图 $\rho_0$。下面按「定义里出现的子群」和「$S(G)$ 自身的子群」两层来讲，每一种都给出棋盘上的含义和数值。

一、定义里出现的两个子群

1. 行格 $\mathbb{Z}^{25}\Delta'$，即被商掉的子群。 它是 $\mathbb{Z}^{25}$ 的子群，元素是 $\Delta'$ 各行的整系数组合 $x\Delta'$。棋盘含义：净效果为零的点击方案。$x_v$ 是格子 $v$「转满一圈」的次数，$x\Delta'$ 就是实现这些整圈所需的点击向量减去邻居送来的推动。例如 $x=\mathbf 1$ 给出四角 2 次、边格 1 次的 20 次点击，$x=104\,\mathbf 1_{(2,2)}$ 的非负代表是「中心 104 次」。商群 $S(G)$ 的每个元素是这个子群的一个陪集：所有产生同一幅箭头图的点击方案。

2. 转子路由群 $\subset\mathrm{Sym}(\mathcal T)$。 $\mathcal T$ 是全部箭头图的集合，$\mathrm{Sym}(\mathcal T)$ 是它上面所有置换构成的群，阶是 $|\mathcal T|!$，大得没有意义。转子路由群是其中由 25 个「点击」置换 $E_v$ 生成的子群，Lemma 3.19 说它同构于 $S(G)$。棋盘含义：$\mathrm{Sym}(\mathcal T)$ 里的一般置换是「任意重排所有局面」，而转子路由群只包含用点击能实现的重排。它是交换的、阶只有 $|\mathcal T|$、作用是自由传递的，这三条都是一般置换没有的。

二、$S(G)$ 自身的子群：局部点击能到达的局面

$S(G)$ 的一个子群 $H$ 在棋盘上就是一族箭头图，满足：含全朝上，且对「把产生 $\rho_1$ 的点击施加到 $\rho_2$ 上」及其撤销封闭。最有用的一类是生成子群。

生成子群 $\langle S\rangle$。 取一组格子 $S$，$\langle S\rangle$ 是只点 $S$ 中格子能从全朝上到达的全部局面。它的阶就是这些局面的个数。

陪集 = 轨道。 从任意局面 $\rho$ 出发只点 $S$ 中的格子，能到达的局面恰好是 $\rho$ 所在的陪集 $\rho\cdot\langle S\rangle$，个数同样是 $|\langle S\rangle|$。于是全部 $|\mathcal T|$ 幅箭头图被分成 $[S(G):\langle S\rangle]$ 个大小相等的轨道，指数就是轨道数。换句话说：限制可点的格子，棋盘的局面空间就按子群的陪集分成互不相通的若干片，每片内部都能互达。

一些具体的 $S$（阶 = 只点这些格子可达的局面数，指数 = 局面空间被分成的片数）：

允许点击的格子 $S$ $\lvert\langle S\rangle\rvert$ 指数
中心 (2,2) 104 313,130,188,800
一个内环角 (1,1) 528 61,677,158,400
一个外角 (0,0) 102,960 316,293,120
中心 + 内环角 (1,1) 54,912 593,049,600
外角 + 中心 823,680 39,536,640
两个相邻外角 (0,0),(0,4) 815,443,200 39,936
四个外角 9,785,318,400 3,328
中心十字（中心及其 4 个邻居） 10,600,761,600 3,072
左上 2×2 块 508,836,556,800 64
内部 3×3 4,070,692,454,400 8
第一行 5 格 32,565,539,635,200 1
最外圈 16 格 32,565,539,635,200 1

结论：

  • 只点中心，只能到达 104 个局面；只点一个角能到 102,960 个，但相对全体仍是沧海一粟。
  • 只点第一行的 5 个格子就能到达每一个局面。 这与「群需要至少 5 个生成元」（不变因子中非 1 的有 5 个，即群的秩为 5）相吻合：5 个格子能生成全群的方案共 6,292 种，去掉 8 个对称后 793 种。4 个格子最好只能做到指数 4（例如第一行前 4 格），即只缺四分之一。
  • 只点内部 3×3，局面空间分成 8 片；只点一个 2×2 块，分成 64 片。

三、挠子群与 Sylow 子群：周期的结构

$k$-挠子群 $S(G)[k]=\{g:kg=0\}$。 棋盘含义：点击方案重复 $k$ 遍就复原的局面。$S(G)[2]$ 的阶是 $2^5=32$，即除全朝上外有 31 个「点两遍复原」的局面，最省的一个只要 10 次点击（见下文“元素的阶”一节）。一般地 $|S(G)[k]|=\prod_i\gcd(d_i,k)$。

Sylow $p$-子群。 $|S(G)|=2^{18}\cdot3^5\cdot5^2\cdot11^2\cdot13^2$，于是

$$ S(G)=P_2\oplus P_3\oplus P_5\oplus P_{11}\oplus P_{13},\qquad |P_2|=262{,}144,\ |P_3|=243,\ |P_5|=25,\ |P_{11}|=121,\ |P_{13}|=169 . $$

$P_p$ 是周期为 $p$ 的幂的那些局面。任何一个局面都唯一地分解为这五部分之和，例如中心一次（阶 $104=8\cdot13$）落在 $P_2\oplus P_{13}$ 里。

倍数子群 $kS(G)$。 $2S(G)$ 是「有平方根」的局面，即能写成某个点击方案做两遍的结果，指数为 $|S(G)[2]|=32$。

四、对称子群：形状对称的局面

正方形的 8 个对称（旋转、翻转）把一幅箭头图变成另一幅，并且与点击可交换，所以它们是 $S(G)$ 的自同构。被所有 8 个对称固定的元素构成一个子群，棋盘含义是形状上具有完全对称性的局面，其阶为 832。只要求 90° 旋转不变的有 3,328 个，只要求左右镜像不变的有 85,662,720 个。单位元代表 $\sigma_1,\sigma_2,\sigma_3$ 和 10 次点击的阶 2 元素都在这个子群里。

五、与分数的关系

分数公式 $\text{总度数}=\sum_v\sigma(v)\tau(v)+\tau^{\mathsf T}(p-r)+\sum r$ 依赖具体的点击向量 $\sigma$，不只依赖它所在的群元素，所以子群本身不决定分数。子群回答的是可达性问题：给定允许点击的格子，哪些局面能出现、局面空间被分成几片；分数问题则要在每个陪集里挑代表。两者合起来，就是「用什么格子、点多少次、能到哪、得几分」的完整图景。

附：计算方法

子群的阶都用 Smith 标准形坐标算：令 $U\Delta'V=\mathrm{diag}(d_i)$，则 $\sigma\mapsto U\sigma \bmod (d_i)$ 把 $S(G)$ 等同于 $\bigoplus\mathbb{Z}_{d_i}$。$\langle S\rangle$ 的阶等于 $\prod d_i$ 除以「由各 $U\mathbf 1_v$（$v\in S$）与 $d_i\mathbf e_i$ 生成的格在 $\mathbb{Z}^5$ 中的指数」，后者用整数行约化几步即得。对称子群的阶是同态 $g\mapsto(rg-g,\ fg-g)$ 的核的阶，用同样的方法算像的大小再相除。

单位元

既然有群，必有单位元。也就是存在某些点击组合，点击后，局面总是回到原先状态。之前提到过一个总点击次数为 52 次的单位元 $I$，它是单位元的唯一常返代表。而点击次数最少的单位元代表只需 20 次，共有三种：

单位元的三个 20 次点击代表

不信的话，你可以在游戏中按以上数字所示，点击对应的格子相应次数，看局面是否回到初始状态。

逆元

既然有群，必有逆元。也就是对任何一种点击组合，都有另一种点击组合可以抵消它的效果，使局面回到之前的状态。有多种计算逆元的方法，以点击“中央一次”为例，求其逆元：

沙堆群的求逆方法：以「点击中央一次」为例

沙堆群求逆有几条现成的路子。核心原因是：求逆在「点击向量」坐标下只是取负号，难点只在于把负向量换成一个非负（可以真的点出来）的代表。下面给出三种快速方法，并算出 5×5「十步万度」中点击中央一次的逆元。

方法一：用整数向量 $x$ 把 $-\sigma$ 抬成非负

任意整数向量 $x$ 都有 $\Delta'x\equiv 0$，所以只要 $\Delta'x\ge\sigma$，

$$ \sigma^{-1}=\Delta'x-\sigma $$

就是逆元的一个非负点击代表。要点击数最少，就最小化

$$ \mathbf 1^{\mathsf T}\Delta'x-\sum_v\sigma_v=\sum_v b_v x_v-\sum_v\sigma_v , $$

其中 $b_v$ 是格子 $v$ 出界的边数（角格 2，边格 1，内部格 0）。与求单位元最少代表时同样的论证：16 个边界格的 $x_v$ 全取 1，再枚举 9 个内部格。这是一个很小的整数规划，瞬间可解。

方法二：筹码图上的公式

设 $m$ 为每格 3 枚的满配置，$\sigma$ 为常返代表，则

$$ \sigma^{-1}=\bigl(3m-(3m)^\circ-\sigma\bigr)^\circ . $$

理由：$3m-(3m)^\circ$ 是一串倒塌的净效果，所以 $\equiv 0$；它 $\ge 2m\ge m+\sigma$，减去 $\sigma$ 后仍 $\ge m$，故稳定化结果是常返的。只需两次稳定化，不用解方程。

方法三：用 Smith 标准形坐标

把 $\sigma$ 映到 $\mathbb{Z}_4\oplus\mathbb{Z}_{16}\oplus\mathbb{Z}_{48}\oplus\mathbb{Z}_{102960}^2$ 的五个坐标，逆元就是每个坐标取负再取模，再乘回去。对单生成元 $g$ 则更简单：

$$ g^{-1}=g^{\,\mathrm{ord}(g)-1}. $$

中心的阶是 104，所以「中心再点 103 次」就是逆元，只是不省。

点击中央一次的逆元

方法一给出唯一的最少代表，共 19 次点击：

$$ \sigma_c^{-1}=\begin{pmatrix} 2&0&0&0&2\\ 0&2&0&2&0\\ 0&0&3&0&0\\ 0&2&0&2&0\\ 2&0&0&0&2 \end{pmatrix} $$

它就是单位元代表 $\sigma_3$ 把中心的 4 改成 3，对应 $x$ 为边界 1、内环 2、中心 3。下界论证：任何代表的边界 $x_v\ge1$，故总数 $\ge 20-1=19$，而边界全 1 的可行内部解只有这一个。

方法二给出同一元素的常返代表：

$$ \begin{pmatrix} 2&3&1&3&2\\ 3&0&3&0&3\\ 1&3&3&3&1\\ 3&0&3&0&3\\ 2&3&1&3&2 \end{pmatrix} $$

验证

三种结果已互相验证：

  • 先点中心一次，再按上面 19 次点击，25 个箭头全部回到朝上（共 140 次旋转）。
  • 「中心一次」的常返代表 $I+\mathbf 1_{(2,2)}$ 与上面的常返配置相加再倒塌，得到单位元 $I$。
  • 把 19 次点击向量加到 $I$ 上稳定化，以及把 $I+103\,\mathbf 1_{(2,2)}$ 稳定化，都得到同一个常返配置。

其中

$$ I=\begin{pmatrix} 2&3&2&3&2\\ 3&2&1&2&3\\ 2&1&0&1&2\\ 3&2&1&2&3\\ 2&3&2&3&2 \end{pmatrix} $$

是沙堆群单位元的常返代表。

元素的阶

沙堆群是有限群，元素必有阶。也就是任何一种点击组合，重复一定次数后，必然会使局面回到原来的状态。以下用三种方法求解“点击中央一次”的阶：

沙堆群中元素的阶：以「点击中央一次」为例

设 $\sigma\in\mathbb{Z}^{25}$ 是一个点击向量，它在沙堆群 $S(G)=\mathbb{Z}^{25}/\mathbb{Z}^{25}\Delta'$ 中的阶，是使 $k\sigma\equiv 0$ 的最小正整数 $k$。$k\sigma\equiv 0$ 的意思是 $k\sigma=\Delta'x$ 对某个整数向量 $x$ 成立，即

$$ x=k\,\Delta'^{-1}\sigma\ \text{是整数向量}. $$

这句话直接给出三种算法。

方法一：看 $\Delta'^{-1}\sigma$ 的分母

$\Delta'^{-1}\sigma$ 是一个有理向量，$k\Delta'^{-1}\sigma$ 为整数当且仅当 $k$ 是所有分量分母的公倍数，所以

$$ \mathrm{ord}(\sigma)=\operatorname{lcm}\{\text{各分量的分母}\} =\frac{\det\Delta'}{\gcd\bigl(\det\Delta',\ \operatorname{adj}(\Delta')\sigma\bigr)} . $$

第二个写法全部在整数里运算，$\operatorname{adj}(\Delta')=\det\Delta'\cdot\Delta'^{-1}$ 是伴随矩阵。只需一次解线性方程组。

对点击中央一次，$\sigma=\mathbf 1_{(2,2)}$，$\Delta'^{-1}\sigma$ 就是 $\Delta'^{-1}$ 的中心列：

$$ \Delta'^{-1}\mathbf 1_{(2,2)}= \begin{pmatrix} \frac{3}{104}&\frac{3}{52}&\frac{1}{13}&\frac{3}{52}&\frac{3}{104}\\[2pt] \frac{3}{52}&\frac18&\frac{5}{26}&\frac18&\frac{3}{52}\\[2pt] \frac{1}{13}&\frac{5}{26}&\frac{23}{52}&\frac{5}{26}&\frac{1}{13}\\[2pt] \frac{3}{52}&\frac18&\frac{5}{26}&\frac18&\frac{3}{52}\\[2pt] \frac{3}{104}&\frac{3}{52}&\frac{1}{13}&\frac{3}{52}&\frac{3}{104} \end{pmatrix} $$

分母有 $104,52,13,8,26$，最小公倍数是 $104$。用整数写法：$\det\Delta'=32{,}565{,}539{,}635{,}200$，伴随矩阵中心列的最大公约数是 $313{,}130{,}188{,}800$，相除得 $104$。

所以 $\mathrm{ord}(\mathbf 1_{(2,2)})=104$。顺带得到 $104\,\Delta'^{-1}\mathbf 1_{(2,2)}$ 就是那个整数向量 $x$：四角 3、角旁 6、边中 8、内环角 13、内环边中 20、中心 46。它的含义是：中心点 104 次的过程中，每一格各倒塌（转满一圈）的次数。

方法二：Smith 标准形坐标

设 $U\Delta'V=\operatorname{diag}(d_1,\dots,d_{25})$，非 1 的不变因子是 $4,16,48,102960,102960$。把 $\sigma$ 的坐标 $c=U\sigma$ 取出，第 $i$ 个坐标在 $\mathbb{Z}_{d_i}$ 中的阶是 $d_i/\gcd(d_i,c_i)$，整体的阶是它们的最小公倍数：

$$ \mathrm{ord}(\sigma)=\operatorname{lcm}_i\frac{d_i}{\gcd(d_i,c_i)} . $$

对中心一次：

$d_i$ $c_i \bmod d_i$ 该分量的阶
4 1 4
16 14 8
48 6 8
102960 5940 52
102960 2970 104

最小公倍数为 $104$。这个方法的好处是 Smith 标准形只需算一次，之后任何元素的阶都是一次矩阵乘法加几个 $\gcd$。

方法三：直接模拟

从全朝上开始反复点中心，数到箭头全部回到朝上为止。阶小的时候这最直观：点 104 次，共 1080 次旋转，97,200°，箭头回到初始状态。但对角格这类阶为 102,960 的元素，模拟就慢了，而方法一、二的代价与阶的大小无关。

几个对照

点击位置 阶
中心 (2,2) 104
内环角 (1,1) 528
内环边中 (1,2) 102,960
外角 (0,0) 102,960
外边中 (0,2) 102,960

群的指数（所有元素阶的最小公倍数）是 $102{,}960=2^4\cdot 3^2\cdot 5\cdot 11\cdot 13$，所以任何单格点击的阶都整除它。

另外，也可以容易地找到阶最小（非平凡）和阶最大的元素。

阶最小（非平凡）：阶为 2 的元素

$k\sigma\equiv0$ 当且仅当 $k\Delta'^{-1}\sigma$ 为整数向量，所以阶为 2 的元素就是 $\sigma=\tfrac12\Delta'x$，其中 $x$ 为整数向量且 $\Delta'x$ 各分量为偶数。模 2 后 $\Delta'\equiv A$（因为 $4\equiv0$），条件变成

$$ A\,x\equiv 0\pmod 2 , $$

即 $x$ 属于邻接矩阵在 $\mathrm{GF}(2)$ 上的核。这个核的维数是 5，恰与五个不变因子都是偶数对应，所以阶为 2 的元素共 $2^5-1=31$ 个。对每个 $x$ 取 $\sigma_0=\Delta'x/2$，再抬成非负的最少点击代表（方法见下）。点击次数最少的那个只要 10 次：

阶为 2 的最少点击元素

对应的 $x$ 是最外圈 16 格加中心。它正好是单位元代表 $\sigma_3$ 的一半。模拟验证：点一遍后箭头不是全朝上（42 次旋转，3780°），点两遍后回到全朝上（共 140 次旋转）。它恰好是一个 10 步的局面：十步万度里存在 10 次点击，重复一遍就把棋盘复原。31 个阶为 2 的元素的最少点击数依次为

$$ 10,16,18,18,18,20,20,20,20,22,22,22,22,22,24,24,24,24,24,24,26,28,28,28,30,30,30,30,30,30,32 . $$

阶最大：阶为群指数 102,960 的元素

有限交换群中必有元素的阶等于指数 $\operatorname{lcm}(d_i)=102{,}960$，判据是它在 $\mathbb{Z}_{102960}$ 分量上的坐标与 102,960 互素。单格点击的阶如下：

$$ \begin{pmatrix} 102960&102960&102960&102960&102960\\ 102960&528&102960&528&102960\\ 102960&102960&104&102960&102960\\ 102960&528&102960&528&102960\\ 102960&102960&102960&102960&102960 \end{pmatrix} $$

所以除中心和内环四角之外，任何一个格子点一次就是阶最大的元素，1 次点击显然已是最少。阶恰为 102,960 的元素共 25,684,239,974,400 个，占全群约 78.9%：随手点一个多重集，大概率就是最大阶。计数方法：阶整除 $m$ 的元素个数为 $\prod_i\gcd(d_i,m)$，再对指数的素因子 $2,3,5,11,13$ 做容斥。

附：最少点击代表的快速算法

求「与 $\sigma_0$ 同类的非负向量中总点击数最少者」不需要枚举。令 $\sigma=\sigma_0+\Delta'y$，总点击数为 $\sum_v\sigma_v=\sum_v\sigma_{0,v}+\sum_v b_v y_v$，随 $y$ 单调不减；而可行集 $\{y\in\mathbb{Z}^{25}:\Delta'y\ge-\sigma_0\}$ 对逐分量取 $\min$ 封闭（$\Delta'$ 是 M 矩阵）。因此最小可行 $y$ 就是最优解，用和里程计一样的迭代即可：

  1. 从下界 $y=\lceil-\Delta'^{-1}\sigma_0\rceil$ 起步；
  2. 反复对每个格子执行 $y_v\leftarrow\max\bigl(y_v,\ \lceil(\sum_{u\sim v}y_u-\sigma_{0,v})/4\rceil\bigr)$，直到不再变化；
  3. 输出 $\sigma=\sigma_0+\Delta'y$。

对 5×5 网格这只需几毫秒。中心逆元的 19 次代表可以用它直接复算；单位元的情形 $\sigma_0=0$ 会得到平凡解 $y=0$，若把起点改为 $y=\mathbf 1$（排除零向量），则得到 20 次的代表 $\sigma_1$。

n步游戏的最佳玩法

最后我们来考虑游戏的最佳玩法。虽然我们有群论的武器，但以上的群模型只刻画一组点击的终态，并不体现过程中的旋转次数。所以寻找最佳解仍然需要程序枚举，不过由于次序无关性，搜索空间大大缩小。

十步万度：1 到 12 步的最佳玩法

一、12 种最佳玩法的图示

下面 12 张图分别是 n=1 到 12 步的最优点击方案。每格大数字是该格的点击次数，右上角小箭头是点完后该格的最终朝向（灰色表示仍朝上）。

1 到 12 步的最佳玩法

n 最优点击多重集（行,列） 旋转数 度数
1 (0,0) 5 450
2 (0,0)×2 11 990
3 (0,0), (0,1)×2 18 1620
4 (0,0), (0,1), (1,1)×2 27 2430
5 (0,0), (0,2), (1,1)×2, (1,2) 38 3420
6 (0,0), (0,2), (1,1)×2, (2,1), (2,2) 49 4410
7 (0,0), (0,3), (1,1), (1,2)×2, (2,1), (2,3) 63 5670
8 (0,0), (0,3), (1,1), (1,2), (2,2)×2, (3,1), (3,3) 78 7020
9 (0,0), (0,4), (1,1), (1,3), (2,2)×2, (2,3), (3,1), (3,4) 99 8910
10 (0,0), (0,4), (1,1), (1,3), (2,2)×2, (3,2), (3,3), (4,1), (4,4) 120 10800
11 (2,2)×11 132 11880
12 (2,2)×10, (3,1), (3,2) 140 12600

n=1 到 4 和 n=8 到 10 各有多个最优解，图中画的是字典序第一个。其余解的情况：n=1 的 5 个解是第一列任意一格；n=2、3、4 的其他解是把图案整体向下平移；n=8、9、10 各有一个以中心为主的第二解，例如 n=10 的另一解是中心 5 次、(2,3) 3 次、(0,0) 与 (4,1) 各 1 次。n=5、6、7、11、12 的最优解唯一。

二、关于最佳玩法的几个结论

n 1 2 3 4 5 6 7 8 9 10 11 12
最优旋转数 5 11 18 27 38 49 63 78 99 120 132 140
第 n 步增量 5 6 7 9 11 11 14 15 21 21 12 8
平均每步 5 5.5 6 6.75 7.6 8.17 9 9.75 11 12 12 11.67
  • 「十步」选得恰到好处。 平均每步得分在 n=10 达到峰值 12 次旋转（1080°），n=11 持平，之后下降。第 9 步和第 10 步的边际收益都是 21 次旋转（1890°），是全表最高；第 11 步骤降到 12，第 12 步只剩 8。无论设计者是否有意，10 步正是收益最高的长度。
  • 「万度」是刚好够得着的目标。 10 步最高 10,800°，而在 131,128,140 个 10 步点击多重集中只有 3,725 个达到 10,000°，占比不到十万分之三。
  • 最优解不能逐步叠加。 除 n=1 到 2 外，任何 n 的最优解都不包含在 n+1 的任何最优解里，贪心策略一定失败。n=10 的解里 (0,0)、(0,4)、(4,4) 三个角都要点，而 n=11 的解却是 11 次全点中心。
  • n=10 的终态是一条螺旋。 点完后 25 个箭头首尾相接，从中心开始顺时针向外盘旋，经过每一格恰好一次，最后从左下角 (4,0) 出界。这是一棵「最长的」生成树，整棵树只有一条路径。

  • 次序不改总分，但能改「戏剧性」。 同样这 10 次点击，若按 (0,0), (0,4), (1,3), (2,2), (2,2), (3,2), (3,3), (4,1), (4,4), (1,1) 的次序，前 9 次只转 31 次，最后一次点击引发连续 89 次旋转，一击 8010°。最平均的次序里单次最长也有 66 次。

    下面的动画按这个次序演示全部 10 次点击，前 9 次每次只转几下，第 10 次点击 (1,1) 后连锁 89 次：

    最后一次点击引发连续 89 次旋转

  • 前 10 步沾了「开局」的光。 长期来看每步最多只值 $1080/104\approx10.4$ 次旋转（反复点中心，104 次一个周期），而前 10 步能做到 12。多出来的部分来自全朝上的初始棋盘储存的「势能」，也就是分数公式里的 $\tau^{\mathsf T}(p-r)$ 项。

  • 解的形状。 n=3 到 10 的最优解都从左上角 (0,0) 出发沿主对角线方向铺开，n=10 的解是一个近似的 X 形：三个角加上两条对角线上的内环格。n=11、12 则完全换成「中心轰炸」。12 步的 140 次旋转恰好与单位元代表 $\sigma_3$ 的旋转数相同，不过只是巧合。

结束语

我在这里放了一个关于游戏与群论知识点的演示，可以体验单位元和逆元的效果，有兴趣的可以玩玩看。

关于十步万度游戏的研究至此也差不多了，我大为惊叹群论的强大。我也非常希望大学里的线性代数或者群论课程的最后一课用这个游戏作为例子，相信学生会学得非常愉快！

参考链接

  1. A. E. Holroyd, L. Levine, K. Mészáros, Y. Peres, J. Propp, D. B. Wilson, Chip-Firing and Rotor-Routing on Directed Graphs, 2008.
  2. Wikipedia: Abelian sandpile model
  3. Wikipedia: Chip-firing game