给定正整数 $n\geqslant 2$，设方恪表
$A=\left[\begin{array}{cccc}{a_{11}} & {a_{12}} & {\cdots} & {a_{1 n}} \\ {a_{21}} & {a_{22}} & {\cdots} & {a_{2 n}} \\ {\vdots} & {\vdots} & {\cdots} & {\vdots} \\ {a_{n 1}} & {a_{n 2}} & {\cdots} & {a_{nn}}\end{array}\right]$ 和 $B=\left[\begin{array}{cccc}{b_{11}} & {b_{12}} & {\cdots} & {b_{1 n}} \\ {b_{21}} & {b_{22}} & {\cdots} & {b_{2 n}} \\ {\vdots} & {\vdots} & {\cdots} & {\vdots} \\ {b_{n 1}} & {b_{n 2}} & {\cdots} & {b_{n n}}\end{array}\right]$
满足 $\left\{a_{i j} | 1 \leqslant i, j \leqslant n\right\}=\left\{b_{i j} | 1 \leqslant i, j \leqslant n\right\}=\left\{1,2, \cdots, n^{2}\right\}$．对 $A$ 实行如下操作：选取位于同一行或同一列的某两个数，交换它们的位置，其余 $n^2-2$ 个数保持不动，称为一次对换．求最小正整数 $m$，使得对任意的 $A、B$，可以经过不超过 $m$ 次对换，把 $A$ 变成 $B$．
$A=\left[\begin{array}{cccc}{a_{11}} & {a_{12}} & {\cdots} & {a_{1 n}} \\ {a_{21}} & {a_{22}} & {\cdots} & {a_{2 n}} \\ {\vdots} & {\vdots} & {\cdots} & {\vdots} \\ {a_{n 1}} & {a_{n 2}} & {\cdots} & {a_{nn}}\end{array}\right]$ 和 $B=\left[\begin{array}{cccc}{b_{11}} & {b_{12}} & {\cdots} & {b_{1 n}} \\ {b_{21}} & {b_{22}} & {\cdots} & {b_{2 n}} \\ {\vdots} & {\vdots} & {\cdots} & {\vdots} \\ {b_{n 1}} & {b_{n 2}} & {\cdots} & {b_{n n}}\end{array}\right]$
满足 $\left\{a_{i j} | 1 \leqslant i, j \leqslant n\right\}=\left\{b_{i j} | 1 \leqslant i, j \leqslant n\right\}=\left\{1,2, \cdots, n^{2}\right\}$．对 $A$ 实行如下操作：选取位于同一行或同一列的某两个数，交换它们的位置，其余 $n^2-2$ 个数保持不动，称为一次对换．求最小正整数 $m$，使得对任意的 $A、B$，可以经过不超过 $m$ 次对换，把 $A$ 变成 $B$．
【难度】
【出处】
2017第16届CGMO试题
【标注】
【答案】
略
【解析】
不妨设 $b_{ij}=(i-1)n+j$，对任意 $i,j$．首先证明两个引理．
引理一：$(1,2, \cdots, n)$ 的任意排列 $\left(a_{1}, a_{2}, \cdots, a_{n}\right)$ 可以经过至多 $n-1$ 次对换，变成 $(1,2, \cdots, n).$
证明：把 $i=1,2, \cdots, n-1$ 依次换到位置 $i$．
引理二：把排列 $(2,3, \cdots, n, 1)$ 变成排列 $(1,2,3, \cdots, n)$，需要经过至少 $n-1$ 次对换．
证明：对 $n$ 应用数学归纳法．当 $n= 2$ 时．结论显然成立．假设可以经过 $m<n-1$ 次对换把 $(2,3, \cdots, n, 1)$ 变成 $(1,2,3, \cdots, n)$，则存在 $k \in\{2,3, \cdots, n \}$ 仅经历了 $1$ 次对换．即从位置 $k-1$ 变到位置 $k$．从而可以经过 $m-1$ 次对换把 $(2, \cdots, k-1, k+1, \cdots, n, 1)$ 变成 $(1,2, \cdots, k-1, k+1, \cdots, n)$，矛盾．
下面证明任意 $2$ 维排列 $A$ 可以经过至多 $2n-1$ 次对换，把第一行变成 $(1, 2, \cdots, n)$．
若 $1,2, \cdots,n$ 所在的列各不相同，则可以经过至多 $n$ 次对换，把它们换至 $A$ 的第一行，再经过至多 $n-1$ 次对换，把 $A$ 的第一行变成 $(1,2, \cdots, n)$．
若 $1,2, \cdots,n$ 中有两个数在同一列，则存在某列（设为第 $k$ 列）不含任何 $1,2, \cdots, n$．把 $k$ 对换至第 $k$ 列，再对换至第 $1$ 行，不会改变 $1,\cdots, k-1, k+1, \cdots, n$ 的位置．
重复上述两类操作，至多 $2n-1$ 次对换，可以把 $A$ 的第一行变成 $(1,2, \cdots, n)$．
同理，至多 $2n-1$ 次对换，可以把 $A$ 的第 $i$ 行变成 $((i-1) n+1,(i-1) n+2, \cdots, i n), i=2,3, \cdots, n-1$．
最后，至多 $n-1$ 次对换，可以把 $A$ 的第 $n$ 行变成 $((n-l)n+l, (n-l)n+2, \cdots,n^2)$．共计至多 $2n(n-1)$ 次对换．
最后证明 $m= 2n(n-1)$ 为所求．设 $A=\left[\begin{array}{ccccc}{n+2} & {n+3} & {\cdots} & {2 n} & {n+1} \\ {2 n+2} & {2 n+3} & {\cdots} & {3 n} & {2 n+1} \\ {\vdots} & {\vdots} & {\cdots} & {\vdots} & {\vdots} \\ {(n-1) n+2} & {(n-1) n+3} & {\cdots} & {n^{2}} & {(n-1) n+1} \\ {2} & {3} & {\cdots} & {n} & {1}\end{array}\right]$．
注意到 $A$ 的第 $i$ 列中的 $n$ 个数都位于 $B$ 的第 $i+1$ 列．根据引理二，把 $A$
变成 $B$ 需要至少 $n(n-1)$ 次水平方向的对换．同理，$A$ 的第 $i$ 行中的 $n$ 个数都位于 $B$ 的第 $i+1$ 行，把 $A$ 变成 $B$ 需要至少 $n(n-1)$ 次竖直方向的对换．
引理一：$(1,2, \cdots, n)$ 的任意排列 $\left(a_{1}, a_{2}, \cdots, a_{n}\right)$ 可以经过至多 $n-1$ 次对换，变成 $(1,2, \cdots, n).$
证明：把 $i=1,2, \cdots, n-1$ 依次换到位置 $i$．
引理二：把排列 $(2,3, \cdots, n, 1)$ 变成排列 $(1,2,3, \cdots, n)$，需要经过至少 $n-1$ 次对换．
证明：对 $n$ 应用数学归纳法．当 $n= 2$ 时．结论显然成立．假设可以经过 $m<n-1$ 次对换把 $(2,3, \cdots, n, 1)$ 变成 $(1,2,3, \cdots, n)$，则存在 $k \in\{2,3, \cdots, n \}$ 仅经历了 $1$ 次对换．即从位置 $k-1$ 变到位置 $k$．从而可以经过 $m-1$ 次对换把 $(2, \cdots, k-1, k+1, \cdots, n, 1)$ 变成 $(1,2, \cdots, k-1, k+1, \cdots, n)$，矛盾．
下面证明任意 $2$ 维排列 $A$ 可以经过至多 $2n-1$ 次对换，把第一行变成 $(1, 2, \cdots, n)$．
若 $1,2, \cdots,n$ 所在的列各不相同，则可以经过至多 $n$ 次对换，把它们换至 $A$ 的第一行，再经过至多 $n-1$ 次对换，把 $A$ 的第一行变成 $(1,2, \cdots, n)$．
若 $1,2, \cdots,n$ 中有两个数在同一列，则存在某列（设为第 $k$ 列）不含任何 $1,2, \cdots, n$．把 $k$ 对换至第 $k$ 列，再对换至第 $1$ 行，不会改变 $1,\cdots, k-1, k+1, \cdots, n$ 的位置．
重复上述两类操作，至多 $2n-1$ 次对换，可以把 $A$ 的第一行变成 $(1,2, \cdots, n)$．
同理，至多 $2n-1$ 次对换，可以把 $A$ 的第 $i$ 行变成 $((i-1) n+1,(i-1) n+2, \cdots, i n), i=2,3, \cdots, n-1$．
最后，至多 $n-1$ 次对换，可以把 $A$ 的第 $n$ 行变成 $((n-l)n+l, (n-l)n+2, \cdots,n^2)$．共计至多 $2n(n-1)$ 次对换．
最后证明 $m= 2n(n-1)$ 为所求．设 $A=\left[\begin{array}{ccccc}{n+2} & {n+3} & {\cdots} & {2 n} & {n+1} \\ {2 n+2} & {2 n+3} & {\cdots} & {3 n} & {2 n+1} \\ {\vdots} & {\vdots} & {\cdots} & {\vdots} & {\vdots} \\ {(n-1) n+2} & {(n-1) n+3} & {\cdots} & {n^{2}} & {(n-1) n+1} \\ {2} & {3} & {\cdots} & {n} & {1}\end{array}\right]$．
注意到 $A$ 的第 $i$ 列中的 $n$ 个数都位于 $B$ 的第 $i+1$ 列．根据引理二，把 $A$
变成 $B$ 需要至少 $n(n-1)$ 次水平方向的对换．同理，$A$ 的第 $i$ 行中的 $n$ 个数都位于 $B$ 的第 $i+1$ 行，把 $A$ 变成 $B$ 需要至少 $n(n-1)$ 次竖直方向的对换．
答案
解析
备注
