China National Team Selection Test

Let $n = 2l + 1$. Since $3 \le n < 2m$, we have $1 \le l \le m - 1$. We first estimate the lower bound of $M$.
By the condition (1), there exists a unique $1 \le i_0 \le m$, such that $a_{i_0, l+1} = m$. Consider $a_{i_0, l}$ and $a_{i_0, l+2}$.

Case 1: At least one of $a_{i_0, l}$ and $a_{i_0, l+2}$ is $m$, and we may assume without loss of generality that $a_{i_0, l}=m$. It follows from the condition (2) that
$$\begin{aligned} a_{i_0, l-1} &\ge m-1,\quad a_{i_0, l-2} \ge m-2,\quad \dots,\quad a_{i_0, 1} \ge m-l+1, \\ a_{i_0, l+2} &\ge m-1,\quad a_{i_0, l+3} \ge m-2,\quad \dots,\quad a_{i_0, 2l+1} \ge m-l. \end{aligned}$$
Thus,
$$\begin{aligned} M &\ge \sum_{j=1}^{n} a_{i_0, j} \\ &\ge (m-l) + 2((m-l+1) + (m-l+2) + \dots + m) \\ &= (2l+1)m - l^2. \end{aligned}$$

Case 2: None of $a_{i_0, l}$ and $a_{i_0, l+2}$ is $m$, and by the condition (1) there exists $1 \le i_1 \le m$, $i_1 \ne i_0$, such that $a_{i_1, l} = m$. It easily follows from the conditions (1) and (2) that $a_{i_1, l+1} = m-1$, $a_{i_1, l+2} = m$. It follows again from the condition (2) that
$$\begin{aligned} a_{i_1, l} &\ge m-1,\quad a_{i_1, l-1} \ge m-2,\quad \dots,\quad a_{i_1, l-(l-1)} \ge m-l+1, \\ a_{i_1, l+2} &\ge m-1,\quad a_{i_1, l+3} \ge m-2,\quad \dots,\quad a_{i_1, l+1} \ge m-l+1. \end{aligned}$$
Thus,
$$\begin{aligned} M &\ge \sum_{j=1}^{n} a_{i_1, j} \ge 2((m-l+1)+(m-l+2)+\dots+(m-1)) \\ &= (2l+1)m - (l^2-l+1). \end{aligned}$$
Combining the above two cases, we have $M \ge (2l+1)m - l^2$.

On the other hand, consider
$$a_{i,j} = f(2i+j) = \begin{cases} 2i+j, & 2i+j \le m, \\ (2m+1)-(2i+j), & m+1 \le 2i+j \le 2m, \\ (2i+j)-2m, & 2m+1 \le 2i+j \le 3m, \\ (4m+1)-(2i+j), & 3m+1 \le 2i+j \le 4m. \end{cases}$$
We shall show that this table of numbers satisfies the required conditions in the problem.
For any $1 \le i \le m$, $1 \le j \le n-1$, if $m \ne 2i+j$, then
$$|a_{i,j} - a_{i,j+1}| = |f(2i+j) - f(2i+j+1)| = 1;$$
if $m = 2i+j$, then
$$|a_{i,j} - a_{i,j+1}| = |f(2i+j) - f(2i+j+1)| = 0.$$
The condition (2) is verified.

We next show that the condition (1) is also fulfilled. In fact, it suffices to show that for any integers $1 \le j \le n$ and $1 \le k \le m$, there exists an integer $1 \le i \le m$ such that $a_{i,j} = k$.
If $j \equiv k \pmod 2$, since $1 \le j \le n$, $1 \le k \le m$ and $n < 2m$,
we have $-2m < k-j < m$, and therefore $-m < \frac{k-j}{2} < m$, and note that $\frac{k-j}{2}$ is an integer. Thus, at least one of $\frac{k-j}{2}$ and $\frac{k-j}{2} + m$ is in the set $\{1, 2, \dots, m\}$; taking this number to be $i$ will do the job.
If $j \not\equiv k \pmod 2$, again since $1 \le j \le n$, $1 \le k \le m$ and $n < 2m$, we have
$$-2m < (2m+1) - (j+k) < 2m,$$
and therefore
$$-m < \frac{(2m+1) - (j+k)}{2} < m,$$
and $\frac{(2m+1)-(j+k)}{2}$ is an integer. Thus, at least one of $\frac{(2m+1)-(j+k)}{2}$ and $\frac{(2m+1)-(j+k)}{2} + m$ is in the set $\{1, 2, \dots, m\}$; taking this number to be $i$ will do the job.

We now estimate $M$ in this case. Since the condition (1) holds, for any $1 \le i_1 < i_2 \le m$, $1 \le j \le n-1$, we have $f(2i_1 + j) \not\equiv f(2i_2 + j)$, i.e. for any integers $x, y$ with the same parity such that $3 \le x < y \le 2m+n$ and $y-x < 2m$, we have $f(x) \ne f(y)$. Thus, for a given $i$, $a_{i,1}, a_{i,2}, \dots, a_{i,2l+1}$ are pairwise distinct, and so are numbers $a_{i,2}, a_{i,3}, \dots, a_{i,2l}$. As a result,
$$\begin{aligned} \sum_{j=1}^{n} a_{i,j} &\le (m-l) + 2((m-l+1) + (m-l+2) + \dots + m) \\ &= (2l+1)m - l^2. \end{aligned}$$
Thus, $M = \max \sum_{1 \le i \le m} a_{i,j} \le (2l+1)m - l^2$.

Therefore, the minimal possible value of $M$ is $(2l+1)m - l^2$ where $n = 2l+1$.