XXVII Olimpiada Matemática Rioplatense

The smallest value that a board can have is $4$, and an example of a board having this value is the following:

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

Let us now show that the value of any board is at least $4$. Assume there is a board where the value is at most $3$. Then, all the numbers from $5$ to $16$ are not neighbors of $1$ and so, $1$ can only have $2$, $3$ and $4$ in adjacent cells. It follows that $1$ cannot be in the interior cells of the board (since these cells have $4$ adjacent cells each). Therefore, $1$ is written in a cell on the border of the board. Let us consider two cases:

Case 1: $1$ is written in a cell on the border but not in a corner. In this case, we may assume that $1$ is written in the cell in row $1$, column $2$ (since the remaining $7$ cases are equivalent by rotations and reflections). As this cell has exactly $3$ adjacent cells (shaded in Figure (a)), the numbers $2$, $3$ and $4$ must be written in them. If $2$ is written as in Figures (b) or (c), we have a contradiction, since $1$ and $2$ combined can only have $3$, $4$ and $5$ as neighbors, but there are more than $3$ adjacent cells. Finally, if $2$ is written as in Figure (d), as $1$, $2$, $3$ and $4$ combined can only have $5$, $6$ and $7$ as neighbors, $3$ and $4$ should be written on the two shaded cells, both neighbors of $1$; we reach a contradiction.



Case 2: $1$ is written in a cell of a corner. In this case, we may assume $1$ is written in row $1$, column $1$ (the remaining $3$ cases are equivalent by rotation). If $2$ is not a neighbor of $1$, then $1$ and $2$ combined have at least $4$ neighbors, which leads to a contradiction, since the only possible neighbors of $1$ and $2$ are $3$, $4$ and $5$. Therefore, we may assume $2$ is written in row $1$, column $2$ (the case where $2$ is written in row $2$, column $1$ is equivalent by reflection). Since $1$, $2$ and $3$ combined can only have $3$ neighbors ($4$, $5$, $6$), then $3$ must be written in row $2$, column $1$, and $4$, $5$ and $6$ must be written in the cells shaded in the figure below. Thus, some number $x\ge 10$ will be written in one of the cells with a $\times$, and therefore, it will be in a cell adjacent to a number $y\le 6$ (written in a shaded cell). This implies that the value of the board is at least $10-6=4$, a contradiction.