朝花夕拾

轻飘飘的旧时光就这么溜走 转头回去看看时已匆匆数年

不可能的铺砌

2010-08-07


依次将 \(1,2,\ldots,n\) 个全等的正六边形摞在一起,得到的图案记作 \(T_n\),下图是 \(n=7\) 的例子:

我们把连在一起的、对称中心在一条直线上的三个正六边形组成的图案叫做一块 "骨头",根据摆放的角度有三种不同的骨头:

我们的问题是:

问题:求证对任何 \(n\)\(T_n\) 都不可能用若干块骨头不重叠不遗漏地恰好铺砌。

这个题目出自 Conway 的论文 " Tiling with polyominoes and combinatorial group theory",在 Thurston 的文章 "Groups, tilings and finite state automata" 中也有讨论。这个题目的难点在于用传统的染色方法是得不出矛盾的,Conway 等人采用的是一个组合群论的途径,即用适当的群元素给铺砌作标记来获得某种铺砌的不变量,并说明区域 \(T_n\) 不满足这个不变量,从而导出矛盾。本文就来介绍这一方法。

由于 \(T_n\) 包含 \(n(n+1)/2\) 个正六边形,因此 \(T_n\) 能被铺砌的必要条件是 \(3\big|n(n+1)\),所以 \(n\equiv1\pmod{3}\) 是肯定不行的,只要再讨论 \(n\equiv0,2\pmod{3}\) 的情形即可。然而 \(n\equiv0\pmod{3}\) 的情形蕴含 \(n\equiv2\pmod{3}\) 的情形:如果对某个 \(n\equiv2\pmod{3}\)\(T_n\) 可以被若干块骨头恰好铺砌,则由于 \(n+1\equiv0\pmod{3}\) 我们可以在此铺砌下方补上由 \((n+1)/3\) 个水平方向的骨头组成的一行使其扩充为 \(T_{n+1}\) 的一个铺砌。所以只要对 \(n\equiv0\pmod{3}\) 的情形证明 \(T_n\) 不可能被若干块骨头铺砌即可。


首先我们考虑平面上由正六边形组成的无穷网格,对每条边根据其与水平方向的夹角标上 \(a,b,c\) 之一,如下图所示:

这个图正是群 \[A=\langle a,b,c\ |\ a^2=b^2=c^2=(abc)^2=1\rangle\] 的 Caley 图,记作 \(\mathcal{G}(A)\)

此外记

\[F=\langle a,b,c\ |\ a^2=b^2=c^2=1\rangle,\]

\(F\) 同构于 3 个 \(\mathbb{Z}_2\) 的自由积:\(F\cong\mathbb{Z}_2\ast\mathbb{Z}_2\ast\mathbb{Z}_2\)

注:在一个群的 Caley 图中,所有顶点都是完全一样的,顶点集与群元素是一一对应的。任选一个基点 \(\ast\) 作为群的单位元,\(v\) 是任一顶点,其对应的群元素为 \(g\),则从 \(\ast\)\(v\) 的任何一条路径都对应于 \(g\) 的一个 word 表示。

\(D\)\(\mathcal{G}(A)\) 中的一个有限区域,其边界为 \(\partial D\)\(\partial D\) 是一条简单闭路径,其定向为逆时针定向。从 \(\partial D\) 上任一点出发,绕着边界一周可以得到此路径的对应的一个 word 表示 \(\pi\)。从不同的点出发得到的 word 表示可能不同,但是它们在 \(F\) 中都是互相共轭的。

注意我们总是把 \(\pi\) 看成是 \(F\) 中的元素 (而不是 \(A\))。三种不同的骨头的边界在 \(F\) 中对应的 word (逆时针读) 分别为 \[\begin{array}{l}w_1=(cb)^3a(cb)^3a,\\w_2=(ac)^3b(ac)^3b,\\w_3=(ba)^3c(ba)^3c.\end{array}\] 如下图所示:

我们称 \(\{w_1,w_2,w_3\}\)\(F\) 中生成的最小正规子群 \(T = \mathcal{N}(\langle w_1,w_2,w_3\rangle)\) 为这三种 "骨头" 的铺砌群。

定理:设 \(D\) 是平面上正六边形网格中的一个有限的、单连通的区域,则 \(D\) 可以被若干骨头恰好铺砌的一个必要条件是 \(\partial D\) 对应的 word \(\pi\) 满足 \(\pi\in T\)

这个定理对更一般的铺砌也适用,而且边的标号可以是自由群中的元素。这里单连通的要求是为了避免 "区域中的洞" 的边界不能表示为群中元素的乘积的情形,比如下面这种:

证明的思路很简单 (虽然说清细节需要花一些篇幅,见 Conway 的文章),对铺砌所使用的骨头的个数归纳即可。如果只用一块骨头就能铺砌,结论显然成立。否则这个铺砌一定可以分成两个单连通的子铺砌,对每个子铺砌使用归纳假设即可。

由于 \(T_n\) 的边界字为 \(w_n=(ac)^n(ba)^n(cb)^n\),所以我们的任务归结为证明对任何 \(n\equiv0\pmod{3}\)\(w_n\notin T\)。按 Conway 的话说,这是把一个困难的问题翻译成了另一个困难的问题,证明最难的部分就在这里。


考虑 \(F\) 的正规子群 \(J=\mathcal{N}(\langle(cb)^3,(ac)^3,(ba)^3\rangle)\),并记 \[T_0 = F/J = \langle a,b,c\ |\ a^2=b^2=c^2=(cb)^3=(ac)^3=(ba)^3=1\rangle.\]

\(T_0\) 的 Caley 图 \(\mathcal{G}(T_0)\) 如下:

可见 \(\mathcal{G}(T_0)\) 的形状与 \(A\) 的 Caley 图 \(\mathcal{G}(A)\) 是一样的,只不过标号不同,\(\mathcal{G}(T_0)\) 中任何两个相邻的正六边形的标号都是不同的,而在 \(\mathcal{G}(A)\) 中所有正六边形的标号都是一样的。我们把 \(\mathcal{G}(T_0)\) 中的三种不同的正六边形分别记作 \(C_1,C_2,C_3\),它们的边界对应的 word 分别是 \((cb)^3,(ac)^3,(ba)^3\)

选定 \(\mathcal{G}(T_0)\) 中的任一顶点 \(\ast\) 作为基点,对 \(F\) 中的任一元素 \(g\),存在 \(\mathcal{G}(T_0)\) 中对应的一个顶点 \(v\) (\(v\) 就是 \(g\)\(T_0\) 中的像对应的顶点),\(g\) 的任一 word 表示对应于一条从 \(\ast\) 出发到达 \(v\) 的路径,不同的 word 表示对应的路径是不同的,但是它们都以 \(\ast\)\(v\) 为起点和终点。特别地,\(J\) 中的元素对应的路径都是从 \(\ast\) 出发又回到 \(\ast\) 的闭路径。

我们来看看 \(T\) 中元素在 \(\mathcal{G}(T_0)\) 中对应的路径是什么样子的。

\(T_1\) 对应的一条路径如下:

这个路径是从 \(\ast\) (图中红点) 出发,逆时针绕左下方的正六边形一圈,再沿着标记为 \(a\) 的边到达右上方的正六边形,顺时针绕着这个正六边形一圈,再沿着标记为 \(a\) 的边回到 \(\ast\)。它关于两个 \(C_1\) 类型的正六边形分别逆时针和顺时针各转了一圈,但是没有环绕过 \(C_2\)\(C_3\) 类型的正六边形,合起来就是它关于每个 \(C_i(i=1,2,3)\) 类型的正六边形的环绕数 (winding number,逆时针一圈算环绕了 +1 次,顺时针一圈算环绕了 -1 次) 都是 0。对于 \(T_2\)\(T_3\) 也有类似的结论成立。于是 \(T\subseteq J\) (这一点从定义也能看出来) 且 \(T\) 中的 word 关于每个 \(C_i\) 型正六边形的环绕数都是 0。

\(K\)\(F\) 中满足如下条件的 word \(w\) 组成的集合:\(w\)\(\mathcal{G}(T_0)\) 中对应的路径 \(p\) 是从 \(\ast\) 出发回到 \(\ast\) 的闭路径,且 \(p\) 关于每个 \(C_i(i=1,2,3)\) 类型的正六边形的环绕数都是 0。不难验证 \(K\) 构成了 \(F\) 的一个正规子群 (两个路径的乘积就是它们首尾相接,因此环绕数仍然是 0;\(w'ww'^{-1}\) 对应路径就是从 \(\ast\) 出发沿着路径 \(w'\) 到达某个顶点 \(v\),在 \(v\) 处沿闭路径 \(w\) 走完再沿着 \(w'^{-1}\) 原路返回 \(\ast\),因此环绕数也都是 0),且我们刚刚说明了 \(T\subseteq K\),所以只要再说明当 \(n\equiv0\pmod{3}\)\(T_n\) 对应的路径的环绕数不全为 0 即可。然而 \(T_n\) 的边界对应的 word 为 \(w_n=(ac)^n(ba)^n(cb)^n\),在 \(n\equiv0\pmod{3}\) 时它对应的路径就是绕着 \(C_1,C_2,C_3\) 分别逆时针转 \(n/3\) 圈,因此其环绕数是 \((n/3,n/3,n/3)\ne(0, 0, 0)\),这就完成了证明。

这里的 \(K\) 实际上是群同态 \(\rho:J\to\mathbb{Z}^3\) 的核,\(\rho\) 的定义如下:对 \(J\) 中任一 word \(w\)\(\rho(w)=(n_1,n_2,n_3)\),其中每个 \(n_i\)\(w\)\(\mathcal{G}(T_0)\) 中对应的闭路径关于 \(C_i\) 类型的正六边形的环绕数。

最后总结一下证明的关键步骤:

  1. 将铺砌问题转化为一个有限表现群中的 word 问题。
  2. 在自由积 \(F\) 而不是 \(A\) 中考虑问题。
  3. 找到 \(F\) 的正规子群 \(J\) 使得 \(J\supseteq T\),且 \(F/J\) 的 Caley 图是平面图。
  4. 利用拓扑中环绕数的概念定义群同态 \(\rho:J\to\mathbb{Z}^3\)\(\rho\) 的核 \(\ker\rho\) 包含 \(T\) 但是不包含 \(w_n\),这就导出了矛盾。