1997年第38届IMO试题

• 知识点

  >

  二试组合部分

略

（1）设 $n>1$ 且存在 $n$ 阶银矩阵 $A$．由于 $S$ 中所有的 $2n-1$ 个数都要在矩阵 $A$ 中出现，而 $A$ 的主对角线上只有 $n$ 个元素，所以至少有一个 $S$ 中的元素 $x$ 不在 $A$ 的主对角线上．取定一个这样的 $x$，对于每个 $i=1,2,\cdots,n$，记 $A$ 的第 $i$ 行和第 $i$ 列中的所有元素合起来构成的集合为 $A$，称为第 $i$ 个"十字"，则 $x$ 在每个 $A_i$ 中恰出现一次，假设 $x$ 位于 $A$ 的第 $i$ 行，第 $j$ 列 $(i\ne j)$，则 $x$ 属于 $A_i$ 和 $A_j$，将 $A_i$ 与 $A_j$ 配对，这样 $A$ 的 $n$ 个"十字"两两配对，从而 $n$ 为偶数．由于 $1997$ 是奇数，故不存在 $n=1997$ 阶银矩阵．
（2）对于 $n=2$，$A=\begin{pmatrix}
1&2\\
3&1
\end{pmatrix}$
即为一个银矩阵．对于 $n=4$，$A=\begin{pmatrix}
1&2&5&6\\
3&1&7&6\\
4&6&1&2\\
7&4&3&1
\end{pmatrix}$
也是银矩阵．
假设存在 $n$ 阶银矩阵 $A$，则按以下方式可构造 $2n$ 阶银矩阵 $D$：$D=\begin{pmatrix}A&B\\
C&A
\end{pmatrix}$，
其中 $B$ 是一个 $n\times n$ 矩阵，它是通过把 $A$ 的每一个元素加上 $2n$ 得到的，而 $C$ 则通过把 $B$ 的主对角线上的元素换成 $2n$ 得到的．
考察 $D$ 的第 $i$ 个"十字"，不妨设 $i\leqslant n$，这时，第 $i$ 个"十字"由 $A$ 的第 $i$ 个"十字"以及 $B$ 的第 $i$ 行和 $C$ 的第 $i$ 列构成，$A$ 的第 $i$ 个"十字"包含元素 $\{1,2,\cdots,2n-1\}$，而 $C$ 则是通过把 $B$ 的主对角线上的元素换成 $2n$ 得到的．
考察 $D$ 的第 $i$ 个"十字"，不妨设 $i\leqslant n$，这时，第 $i$ 个"十字"由 $A$ 的第 $i$ 个"十字"以及 $B$ 的第 $i$ 行的 $C$ 的第 $i$ 列构成，$A$ 的第 $i$ 个"十字"包含元素 $\{1,2,\cdots,2n-1\}$，而 $B$ 的第 $i$ 行和 $C$ 的第 $i$ 列包含元素 $\{2n,2n+1,\cdots,4n-1\}$，所以 $D$ 是一个 $2n$ 阶的银矩阵．