问题描述：三十六军官/拉丁方阵

大数学家欧拉曾提出一个问题：即从不同的6个军团各选6种不同军阶的6名军官共36人，排成一个6行6列的方队，使得各行各列的6名军官恰好来自不同的军团而且军阶各不相同，应如何排这个方队？如果用(1，1)表示来自第一个军团具有第一种军阶的军官，用(1，2)表示来自第一个军团具有第二种军阶的军官，用(6，6)表示来自第六个军团具有第六种军阶的军官，则欧拉的问题就是如何将这36个数对排成方阵，使得每行每列的数无论从第一个数看还是从第二个数看，都恰好是由1、2、3、4、5、6组成。历史上称这个问题为三十六军官问题。
尽管很容易将三十六军官问题中的军团数和军阶数推广到一般的n的情况，而相应的满足条件的方队被称为n阶欧拉方。欧拉曾猜测：对任何非负整数t，n=4t+2阶欧拉方都不存在。t=1时，这就是三十六军官问题，而t=2时，n=10，数学家们构造出了10阶欧拉方，这说明欧拉猜想不对。但到1960年，数学家们彻底解决了这个问题，证明了n=4t+2(t≥2)阶欧拉方都是存在的。下面分析一个简单的证明方法（方法源于《谈_三十六军官问题_的一个错误证明_谭季伟》）：

一个偶数n阶欧拉方阵A有n²个元素，每个元素的（行、列、值1、值2）构成B的一行，可以用一个n²x 4矩阵B来表示，如B的行 ( k, L , i , j) 表示矩阵A中( k ,L) 处的数对是（i，j）。对矩阵B的元素再作如下变换: 1到n的偶数用0代替 ,奇数用1代替，得到矩阵C。由A是欧拉方阵推知矩阵B任意两列的同行元素形成的全部数对中, ( 0 , 0) , ( 0 , 1 ) , ( 1 , 0 ) , ( 1 , 1 )各占四分之一。为简便把具有这样性质的矩阵叫做正交表。
从定义可知，正交表的行数是4的倍数。因改变正交表行的次序仍是正交表,故可以不计较行的次序, 把正交表看作是行的集合。对正交表用1到n的奇数、偶数赋值于0、1上亦能还原为矩阵B再通过矩阵B还原为欧拉方阵A。

命题1：4 X3正交表仅有甲组、乙组两种。且4tX 3正交表（t∈N+）一定是若干个甲组、乙组的并集。

证明：
由于4×3正交表只有4行且( 0 , 0) , ( 0 , 1 ) , ( 1 , 0 ) , ( 1 , 1 )各占四分之一，则任意两列的同行元素形成的全部数对中( 0 , 0) , ( 0 , 1 ) , ( 1 , 0 ) , ( 1 , 1 )均仅出现一次。
先构造4×2正交表，再在此基础上添加第三列得4×3正交表。若第三列首行为x，则有如下4×3正交表甲组与乙组：

接下来证明：4tX 3正交表（t∈N+）一定是若干个甲组、乙组的并集。
设C是4tX3正交表，则C的行共有四种类型: ( 0 , 0，a) , ( 0 , 1，b ) , ( 1 , 0，c ) , ( 1 , 1 ，d)。
这四种类型各占t行，否则例如（0，0，a）有t+1行，C的一、二列含有t+1个（0，0）与（0，0）占1/4要求不符。
当t个a值中有0时，t个b值不能全为0,否则C的一、三列至少含有t十1个(0, 0) ，不符。同理可证c不能全为0，d不能全为1，当a=0时必有b=1，c=1，d=0，为甲组。
当t个a值中有1时，t个b值不能全为1否则C的一、三列至少含有t十1个(0, 1)，不符。同理可证c不能全为1，d不能全为0，当a=1时必有b=0，c=0，d=1，为乙组。
当4tX3正交表删去一个4×3正交表甲组或乙组后4（t-1）×3表中( 0 , 0) , ( 0 , 1 ) , ( 1 , 0 ) , ( 1 , 1 )数目均变为t-1仍为正交表。则对此正交表重复删除一个甲组或乙组操作直至为空集，因此对于4tX3正交表而言一定是若干个甲组、乙组的并集。

命题 2 ：不存在 4 x 4正交表 。

证明：
设C是4X4正交表，任取2行都有( 0 , 0) , ( 0 , 1 ) , ( 1 , 0 ) , ( 1 , 1 )各占四分之一，因此任取C中3列均构成4×3正交表。

若a = x，则b = ~x，否则C的一、四列含有2个（0，x）。且c = ~x，否则C的二、四列含有2个（0，x），但若c = _{x则C的三、四列含有2个（}x，~x）不符，因此a = x不存在4×4正交表。同理取a = ~x，得出不存在4×4正交表。

命题 3 ：8×4 正交表共有十种 ， 为 ( I ) ~ ( V ),和这五种关于S={ （a , b , c, d ) |a , b , c，d =0或1 }的余集 ( I‘) ~ ( V‘ )。

证明：

先证这十种8×4表为正交表，直接验证（I）_{(V)、S为8×4、16×4正交表。于是（I）}（V）分别关于S的余集（I’）~（V’）一定为正交表。
下面证明8×4正交表只有十种。先证含有一行( a0 ，a1 ，a2 ，a3 )的8 x 4正交表C只有(I) ~ (v)这五种, 因为把正交表或非正交表的任一列中的0和1对换仍是正交表或非正交表，S中任一指定元都有数目相同的正交表，现取指定元（0，0，0，0）的8×4正交表讨论。
若C的任意三列含有一个甲组 , 一个乙组，可设C为表A, 因任三列只含一个甲组， ( 0，0， 0 )只能出现一次，故a=b=c=1 ，A的三、四列已有两个 ( 0 ， 1 ) , 故 z =0。同理， x = y = 0 。由任取3列得8×3正交表，8×3正交表为甲组或乙组并集，甲组与乙组中每列的0、1位数相同，故A的第四列要有四个1，故d=1，所以C=(V)。
由C中任意三列至少含有一个甲组，设C为任三列含有两个甲组，由甲组每行的3个分量中0的个数和为奇数，则对于C任取三列其每行的分量均为奇数则这样的行只能为（0，0，0，0），不符，故不存在任意三列均有2个甲组的8×4表。
设C为a = 1的表B，C故a=1，从一、四列看x，b不能同为0或1；从二、四列看y，c不能同为0或1；从三、四列看z，d不能同为0或1。故C=（IV）。
类似推理可得：当 C 的一、二、四列含有两个甲组时，C (Ⅲ) ; 一、三、四列含有两个甲组时，C ~ (Ⅱ) 。二、三、四列含有两个甲组时，C=( I )。至此证得含有一行( 0 0 0 0 ) 的8 X 4正交表只有( I ) ~ ( v ) 五 种。
由此推知含S中任一指定元的8x4正交表都有五种，而不含有该指定元的8×4正交表为这五种正交表关于S的余集亦为五种，因此8×4的正交表只有十种。

命题 4 ：1 2 x 4 正交表共有1 6 种:Ti (i = 0， 1 ， … ， 1 5 ) ，i规定如下用二进制的四 位数表示: i= (a0 , a1 , a2 , a3 )∈S ，S={（a0 , a1 , a2 , a3 ) |a0 , a1 , a2 , a3=0或1 } ,Ti是S的12元可重子集。它含有两个(a0，a1，a2，a3)，六个与(a0，a1，a2，a3)有两个分量相同的行，四个与(a0，a1，a2，a3)有一个分量相同的行，例如T0。

证明：
令R0的第i , j列中, ( ai , aj )出现两次，( ai，~aj ) , ( ~ai， aj) , (_ai，aj )各一次。故余集S\R0的第I , j列中, ( ai , aj)出现了两次，( ai ，~aj ) , (~ai，aj) , (_ai，aj)各三次，于 是Ti = (S\R0) U {a0，a1，a2，a3 }的第i ，j列中(ai，aj) ，(ai，_aj)，(ai，aj)，(_ai，aj)各出现三次，所以Ti是12 x 4 正交表。
下证12×4正交表只有这16种。设C是12x4正交表。首先C必有相同的行。若不然，S\C就是4X4正交表, 此不符合命题2。
其次C没有三行相同。若不然,不失一般性,可设C含有三行 (0，0，0，0)。于是C的任意三列，(0， 0， 0)出现三次，从而含有三个甲组。故C的每行的每三个分量含有奇数个0, 这样的行只能是( 0 0 0 0 )，这又与C是正交表矛盾。由C任意一列0、1互换推广可得含有三行S中任一指定元的C都不是正交表。
再次证：除两行(a0，a1，a2，a3)外，再没有相同的行。设i = 0，有2行（0，0，0，0）相同，因若还有其他两行相同，则这种行的任意三个分量必含有奇数个0，否则对应的三列将含有两个甲组或两个乙组，需16×3正交表才能满足，此12×3不可。而任意三个分量个0的行只能是 (0，0，0，0)，此不为正交表。同理推广得任意一列0、1互换除（a0，a1，a2，a3）外再无相同的行。
综上所述，C有两行相同，其余10行相异，共11种不同行。这11种行构成11×4的非正交表E，且有S\E = R0。因（a0，a1，a2，a3）只有16种取法，则C只有16种。

命题 5： t≥2 , 存在4t×4正交表。任一取4tx4正交表都是若干个8 x 4正交表和1 2 x 4正交表的并集。

证 : 给定t≥2 ,适当选取几个8x4正交表和几个12x4正交表，就可并成4 t x 4 正交表。
设C是4tx4正交表。只要证明C含有一个8X4正交表或12X4正交表, 则命题的后半即告成立类似于命题1的后半段证明 。
设C有r行相同，没有r+1行相同，0<r<t。不失一般性，设C含有r行(0，0，0，0)，于是C的任意三列至少含有r个甲组。若C的某三列(例如一 、二 、三列)含有r+1个甲组，即C含 有(0，0，0，a)，(0，1，1，b) , (1，0，1，c) ，（1，1，0，d）这四种类型的行各有r+1 行。a不能全为0 , 也不能全为1 , 否则C将有r十1行相同，与假设不符。b , c , d 的情形与a同样，于是C有八行构成（IV）。可推知对C某列0、1互换C中原构成（IV）的正交表互换后仍有8×4的正交表。
若C的任意三列均有r个甲组，s个乙组或甲组则r +s = t，则C是r个X和S个Y的并集。

由于C的任意三列含有r个甲组，从而含有r个(0，0，0)，它们全在r个表X中，故S个a、b、c全为1。从C的三、四列看 (0，1)在S个表Y中已出现2S次，故r个z值中有t-2s = r-s个1，r -（r-s）=s个0。同理x，y的情形与z相同。第四列已有r+3s个0，故s个d值中有4t/2-（r+3s）=r-s个0，s-（r-s）=2s-r个1，由此可知C是2s-r个8×4正交表（V）与r-s个T0正交表的并集。推知对C某列0、1互换仍有2s-r个8×4正交表与r-s个16×4正交表。证毕。

因此对于6n = 4t+2（t≥2）欧拉方阵成立。

对于t=1的证明方法还可以通过计算机穷举法实现，具体可参看欧拉猜想的计算机证明——六阶正交拉丁方的不存在性。