给定质数 $p$．设 $A= (a_{ij})$ 是一个 $p \times p$ 的矩阵，满足 $\left\{a_{i j} | 1 \leqslant i, j \leqslant p\right\}=\left\{1,2, \cdots, p^{2}\right\}$．
允许对一个矩阵作如下操作：选取一行或一列，将该行或该列的每个数同时加上 $1$ 或同时减去 $1$．若可以通过有限多次上述操作将 $A$ 中元素全变为 $0$，则称 $A$ 是一个“好矩阵＂．求好矩阵 $A$ 的个数．
允许对一个矩阵作如下操作：选取一行或一列，将该行或该列的每个数同时加上 $1$ 或同时减去 $1$．若可以通过有限多次上述操作将 $A$ 中元素全变为 $0$，则称 $A$ 是一个“好矩阵＂．求好矩阵 $A$ 的个数．
【难度】
【出处】
2012第27届CMO试题
【标注】
【答案】
略
【解析】
由加减法的交换律 和结合律可以将针对同一行或同一列的操作合并进行，并且无需考虑各操作间的次序．
假设所有操作的最终结果是对第 $i$ 行每个数减去 $x_i$，对第 $j $ 列每个数减去 $y_j$，其中，$x_{i}, y_{i}(1 \leqslant i, j \leqslant p)$ 可以是任意整数．
由题设知 $a_{i j}=x_{i}+y_{j}$ 对所有的 $i,j(1 \leqslant i, j \leqslant p )$ 成立．
由于表中各数互不相同，则 $x_{1}, x_{2}, \cdots, x_{p}$ 互不相同，$y_{1}, y_{2}, \cdots, y_{p}$ 也互不相同．不妨设 $x_{1}<x_{2}<\cdots<x_{p}$，这是因为交换 $x_i$ 与 $x_j$ 的值相当于交换第 $i$ 行和第 $j$ 行，既不改变题设也不改变结论．同样，不妨设 $y_{1}<y_{2}<\cdots<y_{p}$．于是，假设数表的每一行从左到右是递增的，每一列从上到下也是递增的．
由上面的讨论知 $a_{11}=1, a_{12}=2$ 或 $a_{21}=2$，不妨设 $a_{12}=2$．否则，将整个数表关于主对角线作对称，不改变题设也不改变结论．
下面用反证法证明：$1 ,2, \cdots,p$ 全在第一行中．
假设 $1,2, \cdots, k(2 \leqslant k<p)$ 在第一行中，$k+ 1$ 不在第一行中．于是，$a_{21}=k+1$．将连续的 $k$ 个整数称为一个＂ 块＂，只需证明：表格的第一行恰由若干个块构成，即前 $k$ 个数为一个块，之后的 $k$ 个数又是一个块，等等．
如若不然，设前 $n$ 组 $k$ 个数均为块，但之后 $k$ 个数不成为块（或之后不足 $k$ 个数），由此知对 $j=1,2, \cdots, n, y_{(j-1) k+1}, y_{(j-1) k+2}, \cdots, y_{j k}$ 构成块从而表格的前 $nk$ 列共可分成 $pn$ 个 $1\times k$ 的子表格 $a_{i,(j-1) k+1}, a_{i,(j-1) k+2}, \cdots, a_{i, j k}(i=1,2, \cdots, p ; j=1,2, \cdots, n)$ 每个子表格中的 $k$ 个数构成块．
现假设 $a_{1, n k+1}=a$，设 $b$ 是最小的正整数，使得 $a +b$ 不在第一行中．则 $b\leqslant k-1$．由于 $a_{2, n k+1}-a_{1, n k+1}=x_{2}-x_{1}=a_{21}-a_{11}=k$，故 $a_{2, n k+1}=a+k$．
从而，$a+b$ 必定在前 $nk$ 列中．这样 $a+b$ 含在某个前面所说的 $1\times k$ 的块中，但 $a、a+k$ 都不在该块中，矛盾．
于是，第一行恰由若干个块构成．特别地，有 $k| p$．但是，$1 <k<p$，而 $p$ 是质数，这导致矛盾．
于是，数表的第一行恰为 $1,2,\cdots,P$，而第 $k$ 行必定为 $(k一1)P+1,(k一1)P+2,\cdots ,kp$．
因此，好矩阵 $A$ 在交换行，交换列，以及关于主对角线作对称下总可转化成唯一形式．
所以，好矩阵的个数等于 $2(p!)^2$．
假设所有操作的最终结果是对第 $i$ 行每个数减去 $x_i$，对第 $j $ 列每个数减去 $y_j$，其中，$x_{i}, y_{i}(1 \leqslant i, j \leqslant p)$ 可以是任意整数．
由题设知 $a_{i j}=x_{i}+y_{j}$ 对所有的 $i,j(1 \leqslant i, j \leqslant p )$ 成立．
由于表中各数互不相同，则 $x_{1}, x_{2}, \cdots, x_{p}$ 互不相同，$y_{1}, y_{2}, \cdots, y_{p}$ 也互不相同．不妨设 $x_{1}<x_{2}<\cdots<x_{p}$，这是因为交换 $x_i$ 与 $x_j$ 的值相当于交换第 $i$ 行和第 $j$ 行，既不改变题设也不改变结论．同样，不妨设 $y_{1}<y_{2}<\cdots<y_{p}$．于是，假设数表的每一行从左到右是递增的，每一列从上到下也是递增的．
由上面的讨论知 $a_{11}=1, a_{12}=2$ 或 $a_{21}=2$，不妨设 $a_{12}=2$．否则，将整个数表关于主对角线作对称，不改变题设也不改变结论．
下面用反证法证明：$1 ,2, \cdots,p$ 全在第一行中．
假设 $1,2, \cdots, k(2 \leqslant k<p)$ 在第一行中，$k+ 1$ 不在第一行中．于是，$a_{21}=k+1$．将连续的 $k$ 个整数称为一个＂ 块＂，只需证明：表格的第一行恰由若干个块构成，即前 $k$ 个数为一个块，之后的 $k$ 个数又是一个块，等等．
如若不然，设前 $n$ 组 $k$ 个数均为块，但之后 $k$ 个数不成为块（或之后不足 $k$ 个数），由此知对 $j=1,2, \cdots, n, y_{(j-1) k+1}, y_{(j-1) k+2}, \cdots, y_{j k}$ 构成块从而表格的前 $nk$ 列共可分成 $pn$ 个 $1\times k$ 的子表格 $a_{i,(j-1) k+1}, a_{i,(j-1) k+2}, \cdots, a_{i, j k}(i=1,2, \cdots, p ; j=1,2, \cdots, n)$ 每个子表格中的 $k$ 个数构成块．
现假设 $a_{1, n k+1}=a$，设 $b$ 是最小的正整数，使得 $a +b$ 不在第一行中．则 $b\leqslant k-1$．由于 $a_{2, n k+1}-a_{1, n k+1}=x_{2}-x_{1}=a_{21}-a_{11}=k$，故 $a_{2, n k+1}=a+k$．
从而，$a+b$ 必定在前 $nk$ 列中．这样 $a+b$ 含在某个前面所说的 $1\times k$ 的块中，但 $a、a+k$ 都不在该块中，矛盾．
于是，第一行恰由若干个块构成．特别地，有 $k| p$．但是，$1 <k<p$，而 $p$ 是质数，这导致矛盾．
于是，数表的第一行恰为 $1,2,\cdots,P$，而第 $k$ 行必定为 $(k一1)P+1,(k一1)P+2,\cdots ,kp$．
因此，好矩阵 $A$ 在交换行，交换列，以及关于主对角线作对称下总可转化成唯一形式．
所以，好矩阵的个数等于 $2(p!)^2$．
答案
解析
备注
