洛奇绵羊问题

今天的问题源自中世纪威尔士人的故事集《Mabinogion》中的一段：

一个男孩来到了一个美丽的山谷，有一条小河在谷中流淌。他看到河一边的草地上有一群黑绵羊，另一边的草地上有一群白绵羊。羊群被施以一种魔法：每个时刻都恰有一只绵羊发出咩咩的叫声。如果发出叫声的是白绵羊，就会有一只黑绵羊趟过小河跑过来并且变成白绵羊；如果发出叫声的是黑绵羊，则会有一只白绵羊趟过小河跑过去并且变成黑绵羊。每个时刻发出叫声的绵羊是完全随机的，整个过程没有绵羊出生或者死亡，一直持续到所有绵羊都变成同一种颜色为止。

问题是这样的：

问题： 如果男孩可以选择在初始时刻 0，或者是每个魔法时刻 1,2,… 结束后将任意数量的白绵羊赶出山谷，那么为了最终得到尽可能多的黑绵羊，他应该采取怎样的策略？

阅读全文

飞船空间跳跃问题

问题： 一艘太空船正在宇宙中做星际航行时，飞船的控制系统出了故障，飞船不能正常地进行空间跳跃，而是只能预先设定一个距离，然后以此距离进行一次方向完全随机的跳跃。现在飞船想要返回太阳系。假设太阳系的半径是 r，发生故障时飞船与太阳的距离为 R>r。好消息是在每个时刻，飞船能够知道自身与太阳系的距离。

求证：不论采用怎样的跳跃策略，飞船返回太阳系的概率都小于 r/R；但是对任何 ϵ>0，可以采取适当的策略，使得飞船返回太阳系的概率大于 (r−ϵ)/R，即 r/R 是最优概率。这个最优策略是什么？

这个问题是 Williams 的教材 Probability with Martingales 中的一道习题，书中没有给出答案。下面是我的解答。我尽可能使论证严格，所以有些啰嗦，可能并不是最简洁的做法。

阅读全文

Schur 多项式与钩长公式

在数学中有那么一些问题，它们的表述简单而初等，但是解决起来却非常困难，往往需要相当的奇思妙想和深刻的工具。围绕这些问题。不同领域的数学相互交织，演绎出许多奇妙的故事。

Young 表就是一个典型的例子，组合数学，表示论，概率论在这里发生了奇妙的交汇。

我们从一个有趣的问题开始：

问题： n 位选民要在一次选举中给 m 个候选人投票，每个选民只能投一票。已知第 i 位候选人最终的得票数为 λi，这里 ∑i=1mλi=n 且 λ1≥⋯≥λm。问题是：有多少种不同的得票序列，使得在投票过程中的任一时刻，对任何的 i<j，第 i 位候选人所得的票数总不少于第 j 位候选人所得的票数？

举个例子，假设有 n=10 位选民和 m=4 个候选人，则得票序列 1,2,1,3,2,1,2,4,3,1 表示第一个选民投票给 1 号，第二个选民投票给 2 号，第三个选民投票给 1 号，第四个选民投票给 3 号，依次类推。符合问题要求的序列必须满足对任何 1≤k≤n 和 1≤i<j≤m，序列的前 k 项中数字 i 出现的次数都大于等于数字 j 出现的次数。

虽然问题的表述很简单，但其实答案相当复杂，叫做钩长公式 (hook length formula)。钩长公式有好几个证明，但我最喜欢的证明是基于 Schur 多项式的理论，接下来就来介绍它。

阅读全文

左 Artinian 环与 Wedderburn-Artin 定理

Wedderburn-Artin 定理最早源于 1907 年 Wedderburn 研究域上有限维结合代数的分类定理。在 Wedderburn 考虑这个问题的时候，Killing 和 Cartan 等人已经完成了有限维复半单 Lie 代数的分类工作，如果读者对有限维 Lie 代数有所了解的话，可能已经知道任何有限维复 Lie 代数 L 有一个极大可解理想 rad(L)，叫做 L 的根 (radical)，去掉这个根的商代数 L/rad(L) 是半单代数，其上的双线性型 Killing 型是非退化的，从而可以通过反复取正交补的方式将 L/rad(L) 分解为一些单代数的直和，然后对单 Lie 代数的结构进行讨论得出其共有 9 种不同的类型。Wedderburn 的思路自然受到了 Killing 等人工作的启发，他采取了类似的套路：

对域 F 上的有限维结合代数 A：

  1. 定义根理想 rad(A)。
  2. 转移到半单代数 A/rad(A)。
  3. 将 A/rad(A) 分解为单代数的直和。
  4. 讨论单代数的结构。

整个路线图如下所示：

总之虽然有限维复李代数和结合代数结构相差很大，但它们的结构定理遵循了类似的套路：拿走可解/幂零的部分，剩下的部分是半单的，而半单是单的直和，于是最终归结为对单成分的结构进行讨论。

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,…,n 个全等的正六边形摞在一起，得到的图案记作 Tn，下图是 n=7 的例子：

把三个连在一起、且对称中心在一条直线上的正六边形组成的图案叫做「骨头」，根据摆放的角度有三种不同的骨头：

求证对任何 n，Tn 都不可能用若干骨头恰好密铺。

Conway 等人的论文里面包含了好几个密铺的问题，上面这个问题只是其中一个。虽然这个问题的表述很简单，但它的解法并不“初等”。这里我称之为“”初等”的方法是染色法。染色法是最常用的论证不可能密铺的手段。它的基本思想是，用一个 Abel 群（一般是有理数域 Q）给平面上每一个正六边形作标记，使得任何骨头覆盖的三个正六边形的标记之和为整数，但是整个区域所有正六边形标记之和不是整数，这样来得出矛盾。

然而，Conway 等人在论文中借助“密铺的同调群”证明了染色方法在这个问题中是无法得出矛盾的。我简要地解释一下原因：染色方法可以成功的必要条件是 Tn 对应的群元素在骨头生成的同调群中不是恒等元，从而无法被密铺。而这个问题中，Tn 对应的群元素在同调群中确实是恒等元（构造适当的 signed tiling 即可）。所以染色法对这个问题无效！

Conway 等人用“密铺的同伦群”给出了不可能密铺的证明。同伦群方法的基本思想是，我们仍然用一个群（未必是 Abel 群）的元素作标记，但是这次是给区域和瓷砖的边界作标记，来获得密铺的某种不变量，并说明 Tn 的边界不满足这个不变量，从而导出矛盾。本文就来介绍这一证明。

阅读全文