
C2b. ${ }^{8}$ An $5 \times 5$ array must be completed with all numbers $\{1,2, \ldots, 25\}$, one number in each cell. Find the maximal positive integer $k$, such that for any completion of the array there is a $2 \times 2$ square (subarray), whose numbers have a sum not less than $k$.


Solution. We will prove that $k_{\max }=45$.

We number the columns and the rows and we select all possible $3^{2}=9$ choices of an odd column with an odd row.

Collecting all such pairs of an odd column with an odd row, we double count some squares. Indeed, we take some $3^{2}$ squares 5 times, some 12 squares 3 times and there are some 4 squares (namely all the intersections of an even column with an even row) that we don't take in such pairs.

It follows that the maximal total sum over all $3^{2}$ choices of an odd column with an odd row is

$$
5 \times(17+18+\cdots+25)+3 \times(5+6+\cdots+16)=1323
$$

So, by an averaging argument, there exists a pair of an odd column with an odd row with sum at most $\frac{1323}{9}=147$.

Then all the other squares of the array will have sum at least

$$
(1+2+\cdots+25)-147=178
$$

But for these squares there is a tiling with $2 \times 2$ arrays, which are 4 in total. So there is an $2 \times 2$ array, whose numbers have a sum at least $\frac{178}{4}>44$. So, there is a $2 \times 2$ array whose numbers have a sum at least 45. This argument gives that

$$
k_{\max } \geq 45
$$

We are going now to give an example of an array, in which 45 is the best possible. We fill the rows of the array as follows:

| 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 |

We are going now to even rows:

In the above array, every $2 \times 2$ subarray has a sum, which is less or equal to 45 . This gives that

$$
k_{\max } \leq 45
$$

A combination of (1) and (2) gives that $k_{\max }=45$.[^6]
