2016 JBMO Problems/Problem 4
Problem
A 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 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 . 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 we can find three of the numbers in consecutive positions, let , , be the numbers in consecutive positions(where ). Due to our hypothesis that in every subarrays each number is used exactly once, in the row above (if there is such a row), precisely above the numbers , , will be the numbers , , in this order. And above them will be the numbers , , and in this order. The same happens in the rows below (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 array, that can be divided into four subarrays, containing thus each number exactly four times, with a total sum of .
It suffices to find how many different ways are there to put the numbers in the first row and the first column . (2)
Denoting by , , , the number of appearances of , , , and respectively in and , the total sum of the numbers in the entire array will be . (3)
If the first, third, and the fifth row contain the numbers and , with denoting the number at the entry , then the second and the fourth row will contain only the numbers , , with denoting the number at the entry . Then and , , , and . Then or , respectively or . (4)
Then is obtained by permuting one of the following quadruples: , , , or . (5)
There are a total of permutations of , permutations of , permutations of , and permutations of . Hence, there are at most different possible total sums. (6)
We can obtain indeed each of these combinations: take three rows alternating with two rows to get ; take three rows alternating with one row and a row to get ; take three rows alternating with two rows to get ; take three rows alternating with two rows to get . (7)
By choosing for example , , , and , we can make all these sums different. (8)
Hence, the maximum possible number of different sums is .
See also
2016 JBMO (Problems • Resources) | ||
Preceded by Problem 3 |
Followed by Last Problem | |
1 • 2 • 3 • 4 | ||
All JBMO Problems and Solutions |