, 2019

The required maximum is $N = 45$, and is achieved, for instance, by the following extremal cell labeling:

In this cell labeling, every $2 \times 2$ square with an odd rank top row has sum $45$, and every $2 \times 2$ square with an even rank top row has sum $44$; the configuration is derived from the considerations below.

Write $n = 5$ and $m = \lfloor n/2 \rfloor = 3$, to show that, if $n$ is odd, then for every injective cell labeling of an $n \times n$ array from $1$ through $n^2$, the labels in some $2 \times 2$ square add up to at least $8m^2 - 11m + 6$ (which is $45$ in the case at hand).

Label rows downward and columns rightward, both from $1$ through $n$, and let $s_{ij}$ be the sum of all numbers labeling the cells in the cross formed by the $i$-th row and the $j$-th column. Formally, letting $a_{ij}$ denote the label assigned to the cell on the $i$-th row and $j$-th column,

$$s_{ij} = \sum_{k=1}^{n} (a_{ik} + a_{kj}) - a_{ij}.$$

Use $\equiv$ to denote congruence modulo $2$ and consider the sum

$$S = \sum_{i,j=1}^{m} s_{2i-1,2j-1} = \sum_{i \equiv j \equiv 1} s_{ij} = (2m-1) \sum_{i \equiv j \equiv 1} a_{ij} + m \sum_{i+j=1} a_{ij};$$

there are $m^2$ ordered pairs $(i, j)$ such that $i \equiv j \equiv 1$, and $2m(n-m)$ ordered pairs $(i, j)$ such that $i + j \equiv 1$.

Finally, use the fact that $n$ is odd, $n = 2m-1$, to tile $C$ by $(m-1)^2$ squares $2 \times 2$ and infer that the numbers in one of these tiles add up to at least

$$\left\lfloor \frac{n^2(n^2+1)}{2(m-1)^2} - \frac{S_0}{m^2(m-1)^2} \right\rfloor = \left\lceil 8m^2 - 11m + 5 + \frac{11}{2} \right\rceil = 8m^2 - 11m + 6,$$

establishing the required lower bound.