SELECTION TESTS FOR THE 2019 BMO AND IMO

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

25	5	24	6	23
11	4	12	3	13
22	7	21	8	20
14	2	15	1	16
19	9	18	10	17

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

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

establishing the required lower bound.