欧拉的三十六军官问题

luyuanhong

欧拉的三十六军官问题

原创 大老李聊数学 大老李聊数学 2024-03-31 07:10 加拿大

欧拉曾经提出过一个有趣的数学问题，这个问题看上去很简单，但是欧拉无法解决。欧拉也曾对这个问题提出一个猜想，但后来这个猜想被证明是错误的。这大概是绝无仅有的，欧拉作出错误猜想的问题，这个问题就是“三十六军官问题”。

1770 年，欧拉的原文是这样阐述这个问题的：

“一个非常有趣的问题，这个问题已经让许多人的消耗了长时间的智慧，使我参与了以下的研究，这些研究似乎开辟了一个新的分析领域，特别是组合研究。这个问题围绕着如何安排 36 名来自 6 个不同团队的军官，使他们在一个正方形中排列，以便在每一行（横向和纵向）中都有 6 名不同军衔和不同团队的军官。”

要理解这个问题，马上可以做一个该问题缩小版的实验，可以叫做“16 军官问题”。请你找一副扑克牌出来，任选 4 种点数，把这 4 个点数的所有 16 张卡牌都找出来。

然后，请你把这 16 张卡牌摆成一个 4×4 的方阵。要求是：每一行和每一列的四张牌的点数和花色都不相同。如果你有兴趣，可以再增加一个条件，即两条对角线上的 4 张牌的点数和花色各不相同。我相信你只要耐心些，不用多久就能排出这样一个正方形，以下是两组解：



欧拉的问题就是把规模从 4 扩大到 6 ，变成 6×6 的方阵。同样要求每行和每列士兵的军团和军衔均不同。听上去这个问题是很简单了，但是欧拉排了半天，找不到合理的排法，所以欧拉把这个问题公开出来了。

欧拉还研究了其他情况。把方阵的每行或列的大小称为方阵的“阶数”，欧拉发现，当阶数是质数或单个质数的幂次时，总是能构造出符合以上条件的方阵。比如 7 是质数；8=2^3 ，是单个质数的幂次；9=3^2 ，也是质数的幂次，所以 7 到 9 阶都可以构造出这样的方阵。

但是 6=2×3 ，它不是的单个质数的幂次。而 10=6×5 ，欧拉也没有找到 10 阶的方阵。另外 2 阶显然也不行。所以欧拉猜测：对所有除以 4 余 2 的阶数，都无法构造出这样的方阵。后来我们可以看到，欧拉猜错了。以下介绍一下个问题的历史。

欧拉的问题中，每个格子里的元素有两个要素：军团和军衔。我们先考虑以下，如果只有一个要素会如何。一个要素情况下，问题变为：用 n 个元素填充 n×n 的方阵，要求每一行每一列的元素各不相同，这种方阵被称为“拉丁方阵”（Latin Square)。

这个名称可能是来源于传说中古罗马的军队作战时，喜欢排成正方形的方阵。而古罗马的官方语言是拉丁文，所以把这种方阵称为“拉丁方阵”。


（古罗马军队喜欢以方阵形式作战）

显然，对任何的阶数，都可以构造出拉丁方阵。一个待研究的问题是，n 阶情况下，可以构造出多少个不同的拉丁方阵？对此问题，目前为止，还没有一个快捷的计算公式。已知的上下界是：



一些已经计算确定的 n 阶拉丁方阵数量表（转自维基百科）：


（Reduced Latin Square 的意思是合并那些可以通过简单置换后，互相转换的方阵）

而数独就是一种 9 阶的拉丁方阵，当然，它的要求比拉丁方阵更强。但是 9 阶的拉丁方阵数量够多，所以数独的题目也是感觉无穷无尽的。



关于拉丁方阵，另外一个有意思的观察是找出拉丁方阵中的“横贯线／transversal”，其定义是：

从一个 n 阶拉丁方阵中找 n 个格子，其中每一行包含一个单元格，每一列包含一个单元格，并且每个符号都被选中一次。


（图中 4 个蓝色格子就是 4 阶拉丁方阵中的一条横贯线）

这种“横贯线”有一个有意思的应用，称为“彩虹匹配”。考虑这一个问题，四对男女参加相亲活动，恰好有四个二人可以参与的游戏。请你安排一下，使得所有人可以在 4 轮里面参与所有四个游戏各一次，并且与其他某个异性恰好一起参与一次游戏。这种匹配方式，就被称为“彩虹匹配”。



但不是所有的拉丁方阵中，都能找出这样的横贯线。留个思考题：

请构造一个 4×4 的拉丁方阵，其中没有横贯线。也就是这个 4×4 的方阵，每一行每一列都恰好包含数字 1 到 4 。但是你无法从中找到 4 格，使得每一行找一格，每一列也找一格，并且 4 格中恰好是 1 到 4 。

关于横贯线，还有有两个猜想：

如果阶数 n 是奇数，那么至少有一个横贯线。

如果阶数 n 是偶数，那么至少有一个 n-1 的“部分横贯线”。意思就是：4 阶的话，至少可以找出 3 个格子符合要求，6 阶的话，找出 5 个格子等等。

以上是关于“拉丁方阵”，再看看欧拉的问题。能看出，欧拉的问题是把两个同样大小的拉丁方阵结合在一起，并且结合在一起后，每一个元素都不同。

当把若干同阶拉丁方组合在一起时，数学中称其为：正交拉丁方（orthogonal Latin squares）。若其中没有重复的元素，则中被称为“互斥正交拉丁方阵”（Mutually orthogonal Latin squares），也经常被简称为“正交拉丁方”。

而两个拉丁方组成的互斥正交拉丁方阵也被称为“希腊-拉丁方”（Graeco-Latin squares）或“欧拉方”（Euler Square）。在以下不混淆的场合，我都简称它们为“正交拉丁方”。

以下是 3、4、5 阶的正交拉丁方阵的例子：



可以检查，其中没有重复的格子，并且每行、每列中对应位置的字母都不同。

欧拉猜想，如果阶数除以 4 余 2 ，就不存在正交拉丁方，但是欧拉证明不了。

1901 年，法国的一位名叫 Gaston Tarry 的业余数学爱好者，通过枚举的方法，证明了不存在 6 阶的正交拉丁方。这在没有计算机的年代，是一个相当漫长的一个过程。我猜想他肯定用了非常久的时间，才枚举完。不管怎样，他部分证明了欧拉的猜想。

非常意外的是，到 1959 年，有数学家利用数学知识，构造出了 22 阶的正交拉丁方。借用这个发现，有人利用当时还处于电子管时代的计算机，找到了一个 10 阶的拉丁方，从而彻底否定了欧拉的猜想。


（1959 年，发现的 10 阶正交拉丁方）

所以，现在正确的结论是：除了 2 阶和 6 阶，其他所有阶数都存在正交拉丁方。

关于正交拉丁方，也有一些其他问题可以研究。比如，对 n 阶情况下，有多少种正交拉丁方？这个问题也很难。

1959 年，刚发现 10 阶正交拉丁方时，美国著名的科普人，马丁·加德纳（Martin Gardner，1914-2010）把这个 10 阶的正交拉丁方作为当月的《科学美国人》杂志的封面。在当期介绍正交拉丁方时，马丁·加德纳称 4 阶的正交拉丁方共有 72 种，这应该是当时的数学家告诉他的，但这是一个错误的数字。

很多年以后，英国的数学家凯瑟琳·奥伦肖（Kathleen Ollerenshaw，1912-2014）发现这却数量应该翻倍，达到 144 种。而这 144 种的每一种有 8 种不同的反射变化，所以正确的答案应该是 144×8=1152 种。

以上的正交拉丁方都是“希腊-拉丁方”，是两个拉丁方的组合。另一个更有意思的考察是，使用三个或更多的拉丁方进行组合，并且仍然保持全局无重复元素。

下图中有 16 个女性名字：



它的特点是每个姓氏在名字的组合在每一行和各一列各出现一次，且全局无重复，所以它就是 3 个 4 阶的拉丁方的正交。

你可能会问，能不能再加一个字，使得每个名字都是四个字，并且仍然是正交拉丁方呢？答案是：做不到，原因是，在 4 阶情况下，最多可以用 3 个拉丁方构成正交。

对 n 阶，最多的，可以组合成正交拉丁方的拉丁方阵数量，被记作 MOLS(n) ，其中 MOLS 就是 mutually orthogonal Latin squares 的缩写。

数学家已经证明，MOLS(n)≤n-1 ，并且 n 为质数或单个质数的幂次时，MOLS(n)=n-1 。以下是前 20 个 MOLS(n) 数值：



n=2 和 6 时，MOLS(n)=1 ，意思就是 2 阶和 6 阶的拉丁方只能单独一个，无法再组合成正交拉丁方。

MOLS(5)=4 ，所以可以构造由 4 个 5 阶拉丁方所组成的正交拉丁方：



你可以检查，图中，每个单元格中的字母，字体，前景颜色和背景颜色都不相同。每一行和列中，对应的四个要素也都不相同。

关于这个欧拉的 36 军官的问题的介绍就到这里。我最大的感想是：这个问题看似简单，但居然让欧拉也犯了错误。这类题目看似是小学生都能做的，但是一旦深入了解，你会发现它的难度可以直接到达最高的难度。这真的是非常好的，可以给小学生进行科普的话题。

参考资料：

https://en.wikipedia.org/wiki/Latin_square

https://en.wikipedia.org/wiki/Mutually_orthogonal_Latin_squares

https://zh.wikipedia.org/zh-hans ... 1%E6%96%B9%E9%99%A3

大老李聊数学