Primary question : Let $n$ be an integer greater than 1. Numbers $1,2,...,n^2$ are placed in an $n\times n$ table, one number per cell. For each such configuration, let $s$ be the maximum value of $a+b$ where $a$ and $b$ are numbers in adjacent cells (sharing sides). What is the minimum possible value of $s$?
Write $S=S_n$ for the minimum value of $s$. Because $n>1$ we obviously have $S\ge n^2+2$ because $n^2$ is adjacent to at least two cells. It is clear also that when $n>3$, $S>n^2+2$ because either $n^2-1$ is adjacent to $\ge 3$ cells or both $n^2$ and $n^2-1$ are in some corners, so one of the $4$ neighbours of $n^2$ and $n^2-1$ is at least $4$. Hence $S\ge n^2+3$ for $n>3$. I know $S_2=6$, $S_3=11$, $S_4=19$. I am not seeing a pattern here.
I was asked for $S_{10}$, so an answer for $n=10$ is already good for me. But it'd be great if $S_n$ is known for an arbitrary $n$.
If you know where this problem came from, plz let me know. The same friend from another question asked me this question but didnt know if this problem is a contest problem from somewhere.
Modified questions :
(1) what is the smallest value of $s$ if we define 'adjacent' to mean 'sharing at least one vertex'? If $S'_n$ is the smallest number of the modified question, it is easy to see that $S'_n\ge n^2+5$ for $n>3$. We have $S'_2=5$, $S_3'=12$. I'd like to know the answer to this question too.
(2) The same question as the primary question but we are filling $1,2,...,mn$ in an $m\times n$ table.
(3) The same question as the modified question (1) but we are filling $1,2,...,mn$ in an $m\times n$ table.
Indeed, a minimum of $n^2 + \lfloor \frac n 2\rfloor + 1$ can be arranged for any $n \geq 3$, as follows, where $m = \lfloor \frac n 2 \rfloor$: \begin{matrix} n^2, & 1, & n^2 - 1, & 2, & n^2 - 2, & \dots \\ m + 1, & n^2 - n + m, & m + 2, & n^2 - n + m + 1, & m + 3, &\dots \\ n^2 - n, & n + 1, & n^2 - n - 1, & n + 2, & n^2 - n - 2, & \dots \\ n + m + 1, & n^2 - 2n + m, & n + m + 2, & n^2 - 2n + m + 1, & n + m + 3, & \dots \\ \dots & \dots & \dots & \dots & \dots & \dots \end{matrix}
As for the optimality, it seems that the following is true:
If this statement is true, then the above arrangement for $n = 2k$ is optimal: we consider the largest $k^2$ numbers $4k^2, 4k^2 - 1, \dots, 3k^2 + 1$. If two of them are adjacent, then the sum is at least $6k^2 + 3$; otherwise, by the above statement, there are at least $k^2 + k$ numbers adjacent to them, among which the largest one must be at least $k^2 + k$. Since this number is adjacent to a number at least $3k^2 + 1$, their sum is at least $4k^2 + k + 1$.
However I'm not able to prove the above statement, although it seems very likely to be true.