Junior Balkan Mathematical Olympiad

We will prove that the maximum number of total sums is $60$. The proof is based on the following claim.

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. Indeed, 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 position, let $x,y,z$ be the numbers in consecutive positions (where $\{x,y,z,t\}=\{a,b,c,d\}$). Due to our hypothesis that in every $2\times 2$ subarray 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,z$ in this order. The same happens in the rows below $R$ (see at the following figure).

$$\left(\begin{array}{ccccc}\bullet & x& y& z& \bullet \\ \bullet & z& t& x& \bullet \\ \bullet & x& y& z& \bullet \\ \bullet & z& t& x& \bullet \\ \bullet & x& y& z& \bullet \end{array}\right)$$

Completing all the array, it easily follows that each column contains exactly two of the numbers and our claim is proven. \hfill (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\times 4$ array, that can be divided into four $2\times 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 $R_1$ and the first column $C_1$. \hfill (2)

Denoting by $a_1,b_1,c_1,d_1$ the number of appearances of $a,b,c$ and respectively $d$ in $R_1$ and $C_1$, the total sum of the numbers in the entire $5\times 5$ array will be $$S=4(a+b+c+d)+a_1\cdot a+b_1\cdot b+c_1\cdot c+d_1\cdot d.(3)$$

In the first, the third and the fifth row contain the numbers $x,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\ge 3$, $y_1\ge 2$, $z_1+t_1=2$, and $z_1\ge 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),(4,3,1,1).(5)$$

There are a total of $\frac{4!}{2!}=12$ permutations of $(5,2,2,0)$, also $12$ permutations of $(5,2,1,1)$, $24$ permutations of $(4,3,2,0)$ and finally, there are $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)

By choosing for example $a=10^3,b=10^2,c=10,d=1$, we can make all these sums different. (8)

Hence, $60$ is indeed the maximum possible number of different sums.

---

Alternative solution.

Alternative version. Consider a regular table containing the four distinct numbers $a,b,c,d$. The four $2\times 2$ corners contain each all the four numbers, so that, if $a_1,b_1,c_1,d_1$ are the numbers of appearances of $a,b,c$ and respectively $d$ in the middle row and column, then $$S=4(a+b+c+d)+a_1\cdot a+b_1\cdot b+c_1\cdot c+d_1\cdot d.(1^{\prime })$$

Consider the numbers $x$ in position $(3,3)$, $y$ in position $(3,2)$, $y^{\prime }$ in position $(3,4)$, $z$ in position $(2,3)$ and $z^{\prime }$ in position $(4,3)$. If $z\ne z^{\prime }=t$, then $y=y^{\prime }$, and in position $(3,1)$ and $(3,5)$ there will be the number $x$. (2')

The second and fourth row can only contain now the numbers $z$ and $t$, respectively the first and fifth row only $x$ and $y$. (3')

Then $x_1+y_1=7$ and $x_1\ge 3$, $y_1\ge 2$, $z_1+t_1=2$, and $z_1\ge 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')

One can continue now as in the first version.