Consider any four pairwise distinct real numbers and write one of these numbers in each cell of a 5×5 array so that each number occurs exactly once in every 2×2 subarray. The sum over all entries of the array is called the total sum of that array. Determine the maximum number of distinct total sums that may be obtained in this way.
Solution
Solution:
We will prove that the maximum number of total sums is 60.
The proof is based on the following claim.
Claim. 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 positions, 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×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).
∙∙∙∙∙xzxzxytytyzxzxz∙∙∙∙∙
Completing all the array, it easily follows that each column contains exactly two of the numbers and our claim has been proven.
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.
Denoting by a1,b1,c1,d1 the number of appearances of a,b,c, and respectively d 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⋅a+b1⋅b+c1⋅c+d1⋅d
If 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 x1+y1=7 and x1⩾3, y1⩾2, z1+t1=2, and z1⩾t1. Then {x1,y1}={5,2} or {x1,y1}={4,3}, respectively {z1,t1}={2,0} or {z1,t1}={1,1}. Then (a1,b1,c1,d1) 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)
There are a total of 2!4!=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.
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). By choosing for example a=103,b=102,c=10,d=1, we can make all these sums different. Hence, 60 is indeed the maximum possible number of different sums.
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 reproduced verbatim; metadata (topic, difficulty) added by this project.