Library / /15 of 17

, 2007

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it Japan

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.

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

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.