Competition problem — Combinatorics

Library / /15 of 20

Combinatorics Difficulty 7.0 National olympiad, round 2 Prove it North Macedonia

A magical square of dimensions $3 \times 3$ is a square with side $3$ , consisting of $9$ unit squares, so that the real numbers written in the unit squares (one number in each unit square) satisfy the property: the sum of the numbers in the unit squares in any row is equal to the sum of the numbers in the unit squares in any column and is equal to the sum of the numbers in the unit squares in the two diagonals.
A rectangle of dimensions $m \times n$ , $m \ge 3$ , $n \ge 3$ is given, which consists of $mn$ unit squares. If in each unit square one number is written in such a way that each square of dimensions $3 \times 3$ is magical, then how many different numbers can be used at most to fill the rectangle?

Solution

We consider the magical square:

$A_1$	$A_2$	$A_3$
$B_1$	$B_2$	$B_3$
$C_1$	$C_2$	$C_3$

\begin{aligned} A_1 + A_2 + A_3 &= B_1 + B_2 + B_3 = C_1 + C_2 + C_3 = A_1 + B_1 + C_1 \\ &= A_2 + B_2 + C_2 = A_3 + B_3 + C_3 = A_1 + B_2 + C_3 = C_1 + B_2 + A_3 = S, \end{aligned}

or, equivalently

\begin{aligned} 4S &= (B_1 + B_2 + B_3) + (A_2 + B_2 + C_2) + (A_1 + B_2 + C_3) + (C_1 + B_2 + A_3) \\ &= (A_1 + A_2 + A_3) + (B_1 + B_2 + B_3) + (C_1 + C_2 + C_3) + 3B_2 = 3S + 3B_2. \end{aligned}

We get

S = 3B_2

. In what follows we will denote the central element

B_2

x

Picture 3.
Next we consider the colored square in Picture 4. Because $2a + c = 3x$ and $2b + d = 3x$ we get that the rectangle is filled in the following way:

Analogously to the way the colored square was filled in Picture 3, we get that $c = a$ , $b = d$ . But then

, from where $a = b = c = d = x$ i.e. all elements of the rectangle have to be equal.
Let $n > 3$ , $m > 3$ . Then, because of the previous discussion, the rectangle of width $3$ and length $m$ has to be filled with one number (Picture 5).

Picture 5.
For the same reasons, the same holds for the colored rectangle and every rectangle obtained by vertical translation.
Finally, if $n = m = 3$ , then the rectangle can be filled with $9$ different numbers. If $n > 3$ or $m > 3$ , then the rectangle can be filled only with a single number.

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.