BMO 2019 Shortlist

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 }\ge 45.(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 }\le 45.(2)$$ A combination of (1) and (2) gives that $k_{\max }=45$.

​