Problem 1844

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 + \dots + 25) + 3 \times (5 + 6 + \dots + 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 + \dots + 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. \qquad (1)$$
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. \qquad (2)$$
A combination of (1) and (2) gives that $k_{\max} = 45$.

$\boxed{}$