Track / Stage 7 / 141 of 300 #2021 of 2444

Problem 2021

National Olympiad second round; IMO P1/P4

Combinatorics Difficulty 7.3 Prove it Japan competition problems · Japan · 2007

There is a grid of $5 \times 5$ . And write the integers $1,2,\ldots,16$ in all the grids (each number can be written only once) in the upper left grid of $4 \times 4$ (♣). About the 4 rows, write the sum of four numbers that are written in each row at the right end of each row. Similarly, about the 4 columns, write the sum of four numbers that are written in each column at the lower end of each column. And nothing is written in the lower right grid. Find the maximum integer $m$ which satisfies the following condition.

Conditions: About step (♣), there exists a way of writing the numbers such that you can choose two numbers $a, b$ which $|a-b| \ge m$ hold from the right end column and also from the lower end row.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Define the numbers written to each grid as shown in the table 1. I can assume that $A_1$ is the minimum and $A_4$ is the maximum in $A_1, A_2, A_3, A_4$ , and that $B_1$ is the minimum and $B_4$ is the maximum in $B_1, B_2, B_3, B_4$ , by rearranging rows and columns appropriately. Now $m \leq A_4 - A_1$ , $m \leq B_4 - B_1$ , so
$\begin{aligned} m &\leq \frac{(A_4 - A_1) + (B_4 - B_1)}{2} \\ &= \frac{1}{2}(a_{4,4} - a_{1,1}) + \frac{1}{2}(a_{4,4} + a_{4,2} + a_{4,3} + a_{2,4} + a_{3,4} - a_{1,1} - a_{1,2} - a_{1,3} - a_{2,1} - a_{3,1}) \\ &\leq \frac{1}{2}(16 - 1) + \frac{1}{2}(16 + 15 + 14 + 13 + 12 - 1 - 2 - 3 - 4 - 5) \\ &= 35 \end{aligned}$
And there exists a way of writing if $m = 35$ (table 2). So the maximum $m$ is $35$ . This is table 1.

$a_{1,1}$	$a_{1,2}$	$a_{1,3}$	$a_{1,4}$	$A_1$
$a_{2,1}$	$a_{2,2}$	$a_{2,3}$	$a_{2,4}$	$A_2$
$a_{3,1}$	$a_{3,2}$	$a_{3,3}$	$a_{3,4}$	$A_3$
$a_{4,1}$	$a_{4,2}$	$a_{4,3}$	$a_{4,4}$	$A_4$
$B_1$	$B_2$	$B_3$	$B_4$

This is table 2.

1	2	5	11	19
3	6	7	12	28
4	8	9	14	35
10	13	15	16	54
18	29	36	53

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.