2016 JBMO Problems/Problem 4

Problem

A $5 \times 5$ table is called regular if each of its cells contains one of four pairwise distinct real numbers, such that each of them occurs exactly once in every $2 \times 2$ subtable.The sum of all numbers of a regular table is called the total sum of the table. With any four numbers, one constructs all possible regular tables, computes their total sums, and counts the distinct outcomes. Determine the maximum possible count.

Solution

Solution 1 (Official solution)

We will prove that the maximum number of total sums is $60$ . The proof is based on the following claim: In a regular table either each row contains exactly two of the numbers or each column contains exactly two of the numbers.

Proof of the Claim:

Let R be a row containing at least three of the numbers. Then, in row $R$ we can find three of the numbers in consecutive positions, let $x$ , $y$ , $z$ be the numbers in consecutive positions(where ${x, y, s, z} = {a, b, c, d}$ ). Due to our hypothesis that in every $2 × 2$ subarrays each number is used exactly once, in the row above $R$ (if there is such a row), precisely above the numbers $x$ , $y$ , $z$ will be the numbers $z$ , $t$ , $x$ in this order. And above them will be the numbers $x$ , $y$ , and $z$ in this order. The same happens in the rows below $R$ (see the following figure).

•	x	y	z	•
•	z	t	x	•
•	x	y	z	•
•	z	t	x	•
•	x	y	z	•

Completing the array, it easily follows that each column contains exactly two of the numbers and our claim is proven. (1)

Rotating the matrix (if it is necessary), we may assume that each row contains exactly two of the numbers. If we forget the first row and column from the array, we obtain a $4 × 4$ array, that can be divided into four $2 × 2$ subarrays, containing thus each number exactly four times, with a total sum of $4(a + b + c + d)$ .

It suffices to find how many different ways are there to put the numbers in the first row $R1$ and the first column $C1$ . (2)

Denoting by $a_1$ , $b_1$ , $c_1$ , $d_1$ the number of appearances of $a$ , $b$ , $c$ , and $d$ respectively in $R1$ and $C1$ , the total sum of the numbers in the entire $5 × 5$ array will be $S = 4(a + b + c + d) + a1 \cdot a + b1 \cdot b + c1 \cdot c + d1 \cdot d$ . (3)

If the first, third, and the fifth row contain the numbers $x$ and $y$ , with $x$ denoting the number at the entry $(1, 1)$ , then the second and the fourth row will contain only the numbers $z$ , $t$ , with $z$ denoting the number at the entry $(2, 1)$ . Then $x_1 + y_1 = 7$ and $x_1 > 3$ , $y_1 > 2$ , $z_1 + t_1 = 2$ , and $z_1 > t_1$ . Then ${x_1, y_1} = {5, 2}$ or ${x_1, y_1} = {4, 3}$ , respectively ${z_1, t_1} = {2, 0}$ or ${z_1, t_1} = {1, 1}$ . (4)

Then $(a_1, b_1, c_1, d_1)$ is obtained by permuting one of the following quadruples: $(5, 2, 2, 0)$ , $(5, 2, 1, 1)$ , $(4, 3, 2, 0)$ , or $(4, 3, 1, 1)$ . (5)

There are a total of $4!/2! = 12$ permutations of $(5, 2, 2, 0)$ , $12$ permutations of $(5, 2, 1, 1)$ , $24$ permutations of $(4, 3, 2, 0)$ , and $12$ permutations of $(4, 3, 1, 1)$ . Hence, there are at most $60$ different possible total sums. (6)

We can obtain indeed each of these $60$ combinations: take three rows $ababa$ alternating with two rows $cdcdc$ to get $(5, 2, 2, 0)$ ; take three rows $ababa$ alternating with one row $cdcdc$ and a row $dcdcd$ to get $(5, 2, 1, 1)$ ; take three rows $ababc$ alternating with two rows $cdcda$ to get $(4, 3, 2, 0)$ ; take three rows $abcda$ alternating with two rows $cdabc$ to get $(4, 3, 1, 1)$ . (7)