, 2024

Combinatorics Difficulty 6.8 National olympiad Prove it Czech Republic

Suppose that we fill a $3 \times 3$ table with natural numbers from $1$ to $9$ using each of them precisely once. After that, we write down the sums in each of the four $2 \times 2$ squares in the ascending order. Determine whether it is possible to obtain the following quadruples of natural numbers:

a) $24$ , $24$ , $25$ , $25$ ,

b) $20$ , $23$ , $26$ , $29$ .

Solution

a) Yes, the following table gives us the desired quadruple of sums.

1	8	2
6	9	5
3	7	4

b) No, it is impossible to get this quadruple. Denote the sum of the four numbers as

S

, we shall proceed by proving that

S \le 98

and then describing all the cases where we get an equality.

Note that in $S$ , the central number contributes four times, the four corner tiles contribute once and the remaining four tiles contribute twice, hence we get:
$S \le 4 \cdot 9 + 2 \cdot (8 + 7 + 6 + 5) + (4 + 3 + 2 + 1) = 98.$
Moreover, it is clear that the upper bound is attained if and only if the number $9$ is in the centre and numbers $1$ , $2$ , $3$ , $4$ are in the corners in some order.

Suppose that we were able to obtain the quadruple $20$ , $23$ , $26$ , $29$ , since the sum of the four numbers is $98$ , the placement of the numbers in the big table would have to follow the rules explained above. But this means that the smallest possible sum of a $2 \times 2$ square is $1 + 5 + 6 + 9 = 21$ , a contradiction, hence we can't obtain this quadruple.

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.