A $5 \times 5$ table is called regular f each of its cells contains one of four pairwise distinct real numbers,such that each of them occurs exactly one 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.
Problem
Source:
Tags: combinatorics
joyce_tan
26.06.2016 15:48
Note that the choice of any 2x3 rectangle determines the rest of the grid. There's 6 options for any such rectangle and each option probably gives a different sum.
silouan
27.06.2016 07:42
This problem proposed by Greece, Silouanos Brazitikos (me)
cjquines0
27.06.2016 14:25
Let the real numbers be $A, B, C, D$. We will not make a distinction between the letter in the table and the value of the number.
For a given table, let $(a, b, c, d)$ be the ordered tuple associated with it, such that there are $a$ $A$s, $b$ $B$s, $c$ $C$s and $d$ $D$s. The only thing that matters here is the number of distinct ordered tuples $(a, b, c, d)$ that are achievable, because then we can choose real numbers such that the total sums $aA + bB + cC + dD$ are pairwise distinct. (For the sake of concreteness, setting $A = 10^0, B = 10^2, C =
10^4, D = 10^6$ is one such assignment, there are many more.)
Claim 1. If one row (resp. column) has only two distinct letters, all rows (resp. columns) have only two distinct letters.
Proof. Without loss of generality, let the two letters be $A$ and $B$, on the same row. (Rotate by $90^{\circ}$ if column.) Then the row will be $ABABA$ or $BABAB$. The conclusion follows: the rows above it and below it must be either $CDCDC$ or $DCDCD$, and the rows adjacent to that must be $ABABA$ or $BABAB$, and so on. $\square$
Claim 2. If one row (resp. column) has three or four distinct letters, then all columns (resp. rows) have only two distinct letters.
Proof. We only need to show that any column (resp. row) only has two distinct letters, and then we will be done by the first claim. But this is clear: suppose without loss of generality these three letters are $ABC$, on the same row. It then follows that there is only one choice for the letters below and above this: $CDA$, which again must be followed by $ABC$, etc. Then the three columns which contain these letters have only two distinct letters, and we are done. $\square$
These claims restrict the number of possible tables. Either a table has only two distinct letters per row, or two distinct letters per column by the first claim. A table cannot have only one letter per row, as that would break the condition. Similarly, if it has three or four letters per row, (resp. column) this forces it to have two letters per column (resp. row) by the second claim.
Without loss of generality, we assume that there are two distinct letters per row, for there exists a bijection between this type and the type which contains two distinct letters per column by rotating $90^{\circ}$. Again without a loss of generality, we assume that the first, third, and fifth rows are composed of only $A$s and $B$s, and the second and fourth rows are composed of only $C$s and $D$s, and then we can simply permute the letters afterward.
Then $\{a, b\}$ can be either $\{6, 9\}$ or $\{7, 8\}$. Similarly, $\{c, d\}$ can be either $\{4, 6\}$ or $\{5, 5\}$. Thus $\{a, b, c, d\} \in \{\{4, 6, 6, 9\}, \{4, 6, 7, 8\}, \{5, 5, 6, 9\}, \{5, 5, 7, 8\}\}$. Then each permutation of $\{a, b, c, d\}$ gives an ordered tuple $(a, b, c, d)$. There are thusly $12 + 24 + 12 + 12 = 60$ possible quadruples $(a, b, c, d)$, and we are done.
yunxiu
28.06.2016 10:02
see 2008 CGMO http://www.artofproblemsolving.com/community/c6h222838p1236872