设有 $mn$ 个实数排成一个 $m$ 行 $n$ 列的阵列 ${\left\{ {{a_{ij}}} \right\}_{m \times n}}$，使得每一行上的 $n$ 个数从左到右都按递增的顺序排列，即对任意 $1 \leqslant i \leqslant m$，当 ${j_1} < {j_2}$ 时有 ${a_{i{j_1}}} \leqslant {a_{i{j_2}}}$．下面把每列上的 $m$ 个数都从上到下按递增的顺序重排得到阵列 ${\left\{ {{a_{ij}}^\prime } \right\}_{m \times n}}$，即对任意的 $1 \leqslant j \leqslant n$，当 ${i_1} < {i_2}$ 时有 ${a_{{i_1}j}}^\prime \leqslant {a_{{i_2}j}}^\prime $，问这个新的阵列 ${\left\{ {{a_{ij}}^\prime } \right\}_{m \times n}}$ 每一行中的 $n$ 个数的大小顺序如何？给出结论并说明理由．
【难度】
【出处】
2013年北京大学等三校联考自主招生保送生测试
【标注】
【答案】
每一行上的 $n$ 个数从左到右还是按递增的顺序排列
【解析】
新的阵列 ${\left\{ {{{a}_{ij}}^\prime} \right\}_{m \times n}}$ 中，每一行上的 $n$ 个数从左到右还是按递增的顺序排列．反证如下：
若有某一行不是这样，不妨设第 $i$ 行上存在 $j < k$ 且 ${a_{ij}}^\prime > {a_{ik}}^\prime $．由新阵列的排法知$${a_{1k}}^\prime \leqslant {a_{2k}}^\prime \leqslant \cdots \leqslant {a_{ik}}^\prime < {a_{ij}}^\prime \leqslant {a_{\left( {i + 1} \right)j}}^\prime \leqslant \cdots \leqslant {a_{mj}}^\prime .$$返回到原阵列 ${\left\{ {{a_{ij}}} \right\}_{m \times n}}$ 讨论，$i$ 个数 ${a_{1k}}^\prime $，${a_{2k}}^\prime $，…，${a_{ik}}^\prime $ 都在原阵列的第 $k$ 列上，
而剩余的 $\left( {m - i + 1} \right)$ 个数 ${a_{ij}}^\prime $，${a_{\left( {i + 1} \right)j}}^\prime $，…，${a_{mj}}^\prime $ 都在原阵列的第 $j$ 列上，
由于这些数共有 $m + 1$ 个而总共有 $m$ 行，所以一定有 ${a_{1k}}^\prime $，${a_{2k}}^\prime $，…，${a_{ik}}^\prime $ 中的某个数与 ${a_{ij}}^\prime $，${a_{\left( {i + 1} \right)j}}^\prime $，…，${a_{mj}}^\prime $ 中的某个数在原阵列的同一行．
故在原阵列的此行上，第 $j$ 列上的数大于第 $k$ 列上的数，与原阵列的排法矛盾．
若有某一行不是这样，不妨设第 $i$ 行上存在 $j < k$ 且 ${a_{ij}}^\prime > {a_{ik}}^\prime $．由新阵列的排法知$${a_{1k}}^\prime \leqslant {a_{2k}}^\prime \leqslant \cdots \leqslant {a_{ik}}^\prime < {a_{ij}}^\prime \leqslant {a_{\left( {i + 1} \right)j}}^\prime \leqslant \cdots \leqslant {a_{mj}}^\prime .$$返回到原阵列 ${\left\{ {{a_{ij}}} \right\}_{m \times n}}$ 讨论，$i$ 个数 ${a_{1k}}^\prime $，${a_{2k}}^\prime $，…，${a_{ik}}^\prime $ 都在原阵列的第 $k$ 列上，
而剩余的 $\left( {m - i + 1} \right)$ 个数 ${a_{ij}}^\prime $，${a_{\left( {i + 1} \right)j}}^\prime $，…，${a_{mj}}^\prime $ 都在原阵列的第 $j$ 列上，
由于这些数共有 $m + 1$ 个而总共有 $m$ 行，所以一定有 ${a_{1k}}^\prime $，${a_{2k}}^\prime $，…，${a_{ik}}^\prime $ 中的某个数与 ${a_{ij}}^\prime $，${a_{\left( {i + 1} \right)j}}^\prime $，…，${a_{mj}}^\prime $ 中的某个数在原阵列的同一行．
故在原阵列的此行上，第 $j$ 列上的数大于第 $k$ 列上的数，与原阵列的排法矛盾．
答案
解析
备注
