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{array}{rl}{a}_{i_0,l-1}& \ge m-1,a_{i_0,l-2}\ge m-2,\dots ,a_{i_0,1}\ge m-l+1,\\ a_{i_0,l+2}& \ge m-1,a_{i_0,l+3}\ge m-2,\dots ,a_{i_0,2l+1}\ge m-l.\end{array}$$ Thus, $$\begin{array}{rl}M& \ge \sum _{j=1}^n{a}_{i_0,j}\\ & \ge (m-l)+2((m-l+1)+(m-l+2)+\cdots +m)\\ & =(2l+1)m-l^2.\end{array}$$

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{array}{rl}{a}_{i_1,l}& \ge m-1,a_{i_1,l-1}\ge m-2,\dots ,a_{i_1,l-(l-1)}\ge m-l+1,\\ a_{i_1,l+2}& \ge m-1,a_{i_1,l+3}\ge m-2,\dots ,a_{i_1,l+1}\ge m-l+1.\end{array}$$ Thus, $$\begin{array}{rl}M& \ge \sum _{j=1}^n{a}_{i_1,j}\ge 2((m-l+1)+(m-l+2)+\cdots +(m-1))\\ & =(2l+1)m-(l^2-l+1).\end{array}$$ 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{array}{ll}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{array}$$ 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(\mathrm{mod}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(\mathrm{mod}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{array}{rl}\sum _{j=1}^n{a}_{i,j}& \le (m-l)+2((m-l+1)+(m-l+2)+\cdots +m)\\ & =(2l+1)m-l^2.\end{array}$$ 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$.