今天的问题源自中世纪威尔士人的故事集《Mabinogion》中的一段：
一个男孩来到了一个美丽的山谷，有一条小河在谷中流淌。他看到河一边的草地上有一群黑绵羊，另一边的草地上有一群白绵羊。羊群被施以一种魔法：每个时刻都恰有一只绵羊发出咩咩的叫声。如果发出叫声的是白绵羊，就会有一只黑绵羊趟过小河跑过来并且变成白绵羊；如果发出叫声的是黑绵羊，则会有一只白绵羊趟过小河跑过去并且变成黑绵羊。每个时刻发出叫声的绵羊是完全随机的，整个过程没有绵羊出生或者死亡，一直持续到所有绵羊都变成同一种颜色为止。
问题是这样的：
问题： 如果男孩可以选择在初始时刻 \(0\)，或者是每个魔法时刻 \(1,2,\ldots\) 结束后将任意数量的白绵羊赶出山谷，那么为了最终得到尽可能多的黑绵羊，他应该采取怎样的策略？
问题： 一艘太空船正在宇宙中做星际航行时，飞船的控制系统出了故障，飞船不能正常地进行空间跳跃，而是只能预先设定一个距离，然后以此距离进行一次方向完全随机的跳跃。现在飞船想要返回太阳系。假设太阳系的半径是 \(r\)，发生故障时飞船与太阳的距离为 \(R>r\)。好消息是在每个时刻，飞船能够知道自身与太阳系的距离。
求证：不论采用怎样的跳跃策略，飞船返回太阳系的概率都小于 \(r/R\)；但是对任何 \(\epsilon>0\)，可以采取适当的策略，使得飞船返回太阳系的概率大于 \((r-\epsilon)/R\)，即 \(r/R\) 是最优概率。这个最优策略是什么？
这个问题是 Williams 的教材 Probability with Martingales 中的一道习题，书中没有给出答案。下面是我的解答。我尽可能使论证严格，所以有些啰嗦，可能并不是最简洁的做法。
在数学中有那么一些问题，它们的表述简单而初等，但是解决起来却非常困难，往往需要相当的奇思妙想和深刻的工具。围绕这些问题。不同领域的数学相互交织，演绎出许多奇妙的故事。
Young 表就是一个典型的例子，组合数学，表示论，概率论在这里发生了奇妙的交汇。
我们从一个有趣的问题开始：
问题： \(n\) 位选民要在一次选举中给 \(m\) 个候选人投票，每个选民只能投一票。已知第 \(i\) 位候选人最终的得票数为 \(\lambda_i\)，这里 \(\sum_{i=1}^m\lambda_i=n\) 且 \(\lambda_1\geq\cdots\geq\lambda_m\)。问题是：有多少种不同的得票序列，使得在投票过程中的任一时刻，对任何的 \(i<j\)，第 \(i\) 位候选人所得的票数总不少于第 \(j\) 位候选人所得的票数？
举个例子，假设有 \(n=10\) 位选民和 \(m=4\) 个候选人，则得票序列 \[1, 2, 1, 3, 2, 1, 2, 4, 3, 1\] 表示第一个选民投票给 1 号，第二个选民投票给 2 号，第三个选民投票给 1 号，第四个选民投票给 3 号，依次类推。符合问题要求的序列必须满足对任何 \(1\leq k\leq n\) 和 \(1\leq i<j\leq m\)，序列的前 \(k\) 项中数字 \(i\) 出现的次数都大于等于数字 \(j\) 出现的次数。
虽然问题的表述很简单，但其实答案相当复杂，叫做钩长公式 (hook length formula)。钩长公式有好几个证明，但我最喜欢的证明是基于 Schur 多项式的理论，接下来就来介绍它。
Wedderburn-Artin 定理最早源于 1907 年 Wedderburn 研究域上有限维结合代数的分类定理。在 Wedderburn 考虑这个问题的时候，Killing 和 Cartan 等人已经完成了有限维复半单 Lie 代数的分类工作，如果读者对有限维 Lie 代数有所了解的话，可能已经知道任何有限维复 Lie 代数 \(L\) 有一个极大可解理想 \(\mathrm{rad}(L)\)，叫做 \(L\) 的根 (radical)，去掉这个根的商代数 \(L/\mathrm{rad}(L)\) 是半单代数，其上的双线性型 Killing 型是非退化的，从而可以通过反复取正交补的方式将 \(L/\mathrm{rad}(L)\) 分解为一些单代数的直和，然后对单 Lie 代数的结构进行讨论得出其共有 9 种不同的类型。Wedderburn 的思路自然受到了 Killing 等人工作的启发，他采取了类似的套路：
对域 \(F\) 上的有限维结合代数 \(A\)：
- 定义根理想 \(\mathrm{rad}(A)\)。
- 转移到半单代数 \(A/\mathrm{rad}(A)\)。
- 将 \(A/\mathrm{rad}(A)\) 分解为单代数的直和。
- 讨论单代数的结构。
整个路线图如下所示：
总之虽然有限维复李代数和结合代数结构相差很大，但它们的结构定理遵循了类似的套路：拿走可解/幂零的部分，剩下的部分是半单的，而半单是单的直和，于是最终归结为对单成分的结构进行讨论。
Wedderburn-Artin 定理的过程比较长，不过在头脑中事先明确这条主线，理解整个证明并不是一件困难的事情。
本文将针对左 Artinian 环的情形证明 Wedderburn-Artin 定理。我将采用上面 Wedderburn 的证明途径，而不是现在教科书上普遍使用的 Jacobson 根方法。我主要参考了 Curtis 和 Reiner 的经典 (Curtis and Reiner 1962)，Herstein 的精彩小书 (Herstein 1994)，以及林节玄的 (Lam 2001)。C&R 的书是个大部头，但它总是从最基本的概念讲起，叙述清楚易懂，对新手非常友好。Herstein 的书则是另一种风格，主线简单，节奏很快，短短几章就讲到了中心单代数和 Galois 上同调。林节玄的书风格则更为现代一些，我没有细读，不多评价。
Conway 等人在论文 (Conway and Lagarias 1990) 中提出了下面的问题：
问题： 依次将 \(1,2,\ldots,n\) 个全等的正六边形摞在一起，得到的图案记作 \(T_n\)，下图是 \(n=7\) 的例子：
把三个连在一起、且对称中心在一条直线上的正六边形组成的图案叫做「骨头」，根据摆放的角度有三种不同的骨头：
求证对任何 \(n\)，\(T_n\) 都不可能用若干骨头恰好密铺。
Conway 等人的论文里面包含了好几个密铺的问题，上面这个问题只是其中一个。虽然这个问题的表述很简单，但它的解法并不“初等”。这里我称之为“”初等”的方法是染色法。染色法是最常用的论证不可能密铺的手段。它的基本思想是，用一个 Abel 群（一般是有理数域 \(\mathbb{Q}\)）给平面上每一个正六边形作标记，使得任何骨头覆盖的三个正六边形的标记之和为整数，但是整个区域所有正六边形标记之和不是整数，这样来得出矛盾。
然而，Conway 等人在论文中借助“密铺的同调群”证明了染色方法在这个问题中是无法得出矛盾的。我简要地解释一下原因：染色方法可以成功的必要条件是 \(T_n\) 对应的群元素在骨头生成的同调群中不是恒等元，从而无法被密铺。而这个问题中，\(T_n\) 对应的群元素在同调群中确实是恒等元（构造适当的 signed tiling 即可）。所以染色法对这个问题无效！
Conway 等人用“密铺的同伦群”给出了不可能密铺的证明。同伦群方法的基本思想是，我们仍然用一个群（未必是 Abel 群）的元素作标记，但是这次是给区域和瓷砖的边界作标记，来获得密铺的某种不变量，并说明 \(T_n\) 的边界不满足这个不变量，从而导出矛盾。本文就来介绍这一证明。
当前网速较慢或者你使用的浏览器不支持博客特定功能，请尝试刷新或换用Chrome、Firefox等现代浏览器