握住科学钥匙 打开科学之门

首页 > 正文

三十六军官问题

2019-01-06 09:17  来源: 新华网

传说在18世纪,普鲁士国王决定举行一次盛大的阅兵典礼,计划从6支部队中,每个部队选出6名不同等级的军官各1名,合计36人,组成一个“6×6”的方阵,要求每行每列都必须有各个部队和各种军衔的代表,既不准重复,也不能遗漏。这件事情看来很好办,不料命令传达下去之后,却根本无法执行。阅兵司令接二连三地吹哨子,喊口令,排来排去,始终不符合国王的要求。事后,国王对这件事情始终耿耿于怀,然后他就亲自编排,可是无论如何编排,都达不到他当初的要求。于是他就去请教当时欧洲一流的大数学家欧拉,希望能找出一个解决方案。

欧拉先从最简单问题入手,当n=3 (即有3种部队、3种级别)的方阵,用A、B、C表示不同部队,用a、b、c表示不同级别的军官,如图1。这个方阵的特点是每行每列中A、B、C各有一个,a、b、c也各有一个,并且不出现重复。

类似的他又写出n=4、n=5的方阵,如图2、图3。它们均满足条件且又都不重复。

当n=6的情形,既找不到合乎要求的方阵,又不能证明它不存在,但他估计是不存在的。1782年欧拉是这样谈论这个问题的:“我已经试验研究了很多次,我确信不可能作出两个六阶的,并且对于10、14,…以及奇数2倍的阶数都是不可能的。”

欧拉认为:4n + 2阶欧拉方阵不存在。被后人称之为“欧拉方阵猜想”。

欧拉“36军官问题”是组合学中组合设计的先声。由于构造正交拉丁方的困难,欧拉方阵猜想的研究进展很慢。直到1910年,加斯顿•塔里在他的兄弟赫伯特•塔里的帮助下,列出了全部六阶拉丁方,验证了它们当中任两个都是不正交的,从而证实了n=6时欧拉猜想是正确的。但人们认为塔里兄弟没有从理论上加以证明,这是一个很大的缺陷,而且随着阶数增大,列出全部拉丁方的方法也不可取,即使列出全部拉丁方,要验证每两个是否正交就更加困难。

1959年4月,印度数学家玻色和斯里克汉德构造了两个22阶正交拉丁方,从而构造出22阶欧拉方阵,否定了欧拉猜想。不久,他们证明出:除n=2、6、14、26外,n阶欧拉方阵都是存在的。接着,美国数学家帕克又构造出14阶与26阶的欧拉方阵,至此,欧拉方阵猜想只对当n=2、6成立,其余都是错的。这个否定的结果是人们在180年的努力中未曾想到的。

类似这样的方阵,在工农业生产和科学实验领域都有极其广泛的应用,利用它能够以较少的实验次数获得较好的结果,还能节省原料,改进配方等等。

本作品为“科普中国-科学原理一点通”原创,转载时务请注明出处。

 

作者: 齐月园   [责任编辑: 李浩]

相关稿件

数学,排列