Belorusija 2012

Answer: $mn-6$. Let $A$ be the maximal number in the table and $a$ be the minimal number. Consider any cell $k$ of the table where $A$ stands. Since $A$ is the arithmetic mean of the number in some two neighboring cells $k_1$ and $k_2$. But all numbers in the table are no greater than $A$, the numbers in $k_1$ and $k_2$ are equal to $A$. Since $k_1$ and $k_2$ have the common sides with $k$, they have no common side, so they are not neighbors. Since $A$ stands in $k_1$, number $A$ must stand in two cells having the common sides with $k_1$. One of them is cell $k$ and the other cell is different from $k_2$ ($k_1$ and $k_2$ are not neighbors). It follows that $A$ stands in at least 4 different cells.

Similarly, $a$ stands in at least 4 different cells.

Thus, the maximal and minimal numbers stand in at least 8 different cells of the table. The number of all cells is $mn$, so at most $mn-8+2=mn-6$ different numbers can stand in the table. We construct the example for $mn-6$ different numbers.



We mark two $2\times 2$ neighboring squares (see the fig.) and join these squares with the line passing through any cell of the table exactly one time as it is shown in the figures depending on the parity of $m$ and $n$. We stand 1 in all cells of the first square and stand $mn-6$ in all cells of the second square. We move along the line from the cell with 1 to the cell with $mn-6$. We put in each cell of the line the number which is 1 greater than the number in the previous cell. It is easy to see that the obtained table satisfies the condition and has exactly $mn-6$ different numbers.