If we place $1$ to $n^2$ in an $n\times n$ table, what is the smallest $s$ where $s$ is the max of $a+b$ where $a,b$ are numbers in adjacent cells? 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.
 A: 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:

On a $2k \times 2k$ grid, if we mark $k^2$ cells such that no two are adjacent to each other, then the number of cells that are adjacent to at least one marked cell is at least $k^2 + k$.

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.
