$n$阶方阵 有两个相邻元素 差≥$n$

hbghlyj

The Art of Mathematics: Coffee Time in Memphis, page 76

21. Neighbours in a Matrix
Every $n \times n$ matrix whose entries are $1,2, \ldots, n^2$ in some order has two neighbouring entries (in a row or in a column) that differ by at least $n$.

Proof. Let us call a row or column of our matrix a line. Let $m$ be the smallest integer such that some line is filled with numbers at most $m$. We may assume that this line is the first row and $m$ is in the $(1,1)$ position of this row. Since none of columns two, three, ... $n$, is filled with the numbers $1,2, \ldots, m$, every column, with the possible exception of the first, has two neighbouring entries, one of which is at most $m-1$ and the other at least $m+1$. Consequently, the difference of at least one of these $n-1$ pairs is at least $n$ : indeed, the maximum of the $n-1$ numbers in these pairs that are greater than $m$ is at least $m+n-1$, and the other number in this pair is at most $m-1$.$□$

hbghlyj

译:
设矩阵为$(a_{ij})$,设$\displaystyle m_j=\max_ia_{ij}$为第$j$列最大的元素,设$\displaystyle m=\min_jm_j$,
不妨设$m$在第一列,则第$j$列$(j\in\{2,3,⋯,n\})$不能全由$1,2,⋯,m$组成(否则这一列的最大元素将$<m$),
因此必有一个$≤m-1$的元素$b_j$,与一个$≥m+1$的元素$c_j$相邻.
设$c_k=\max\{c_j:j=2,3,⋯,n\}$,则$c_k≥m+n-1$,而$b_k≤m-1$,故$|b_k-c_k|≥n$.