1999第14届CMO试题

• 知识点

  >

  二试组合部分

略

选择 $4\times 4\times 4$ 大正方体的某个 $4\times 4$ 侧面作为基准面．将大正方体划分成平行于基准面的四层（每层为 $4\times 4\times 1$ 方体），依次用 $1,2,3,4$ 给各层编号．将各个涂红单位方体投影到基准面上并在投影方格内填写该红色单位方体所在的层号．这样，我们得到一个 $4\times 4$ 方格表，每格填写 $\{1,2,3,4\} $ 中的一个数，填同样数的方格既不同行也不同列．这样一个 $4\times 4$ 方格表被称为一个 $4$ 阶拉丁方．反之，每一个 $4$ 阶拉丁方唯一决定了符合题目要求的一种涂色法，不同的拉丁方决定不同的涂色法．因此，题目转化为确定总共有多少不同的 $4$ 阶拉丁方．
约定如表1 那样用 $(i,j)$ 标示 $4\times 4$ 方格表中各单位方格的位置对于 $(1,2,3,4)$ 的任一排列 $(a,b,c,d)$，我们来考察如图1 所示的拉丁方的个数，为此目的，先考察如图2所示的拉丁方的个数．图2的 $(2,2)$ 方格可填写 $|a, c, d|$ 中的任一个数，以下分别考察这三种情形．
（i）设图2的 $(2,2)$ 方格填写 $a$．对此情形，在 $(2,3)$ 和 $(3,2)$ 方格内只能填写 $d$．接着在 $(2,4)$ 和 $(4,2)$ 方格内只能填写 $c$；然后在 $(3,3)$ 方格内可以填写 $a$ 或 $b$．当 $(3,3)$ 方格选定一种填写之后，剩下 $3$ 个方格的填写法唯一确定．因此，相应本情形的拉丁方恰有 $2$ 个．
（ii）设图2的 $(2,2)$ 方格填写 $c$．
对此情形，在 $(2,4)$ 和 $(4,2)$ 方格内只能填写 $a$；接着在 $(2,3)$ 和 $(3,2)$ 方格内只能填写 $d$；然后在 $(3,4)$ 和 $(4,3)$ 方格内可以填写 $b$．在这些方格填写后，剩下方格的填写法唯一确定．因此，相应本情形的拉丁方恰有 $1$ 个．
（iii）设图2的 $(2,2)$ 方格填写 $d$．
与（ii）所述情形类似，对本情形可以判定只有唯一的填写法，即恰有一个拉丁方．根据以上讨论，如图2所示的那类拉丁方恰有 $4$ 个．每个这样的拉丁方通过第 $2,3,4$ 行的置换产生 $3!$ 个不同的如图1所示的那类拉丁方．因此，如图1所示的那类拉丁方恰有 $4\times 3!$ 个．最后，因为排列 $(a,b,c,d)$ 有 $4!$ 个，所以 $4$ 阶拉丁方总共有 $(4!)^2$ 个．故题目所述的 $16$ 个涂色方体的选取办法总共有 $(4!)^2 = 576$ 种