Maths Olympiad Prep

Library / /16 of 16

Combinatorics Difficulty 7.4 National Olympiad, round 2 Prove it JBMO

Problem:

Consider any four pairwise distinct real numbers and write one of these numbers in each cell of a 5×55 \times 5 array so that each number occurs exactly once in every 2×22 \times 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 6060.

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 RR be a row containing at least three of the numbers. Then, in row RR we can find three of the numbers in consecutive positions, let x,y,zx, y, z be the numbers in consecutive positions (where {x,y,z,t}={a,b,c,d}\{x, y, z, t\} = \{a, b, c, d\}). Due to our hypothesis that in every 2×22 \times 2 subarray each number is used exactly once, in the row above RR (if there is such a row), precisely above the numbers x,y,zx, y, z will be the numbers z,t,xz, t, x in this order. And above them will be the numbers x,y,zx, y, z in this order. The same happens in the rows below RR (see at the following figure).

(xyzztxxyzztxxyz) \left(\begin{array}{lllll} \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 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×44 \times 4 array, that can be divided into four 2×22 \times 2 subarrays, containing thus each number exactly four times, with a total sum of 4(a+b+c+d)4(a+b+c+d). It suffices to find how many different ways are there to put the numbers in the first row R1R_1 and the first column C1C_1.

Denoting by a1,b1,c1,d1a_1, b_1, c_1, d_1 the number of appearances of a,b,ca, b, c, and respectively dd in R1R_1 and C1C_1, the total sum of the numbers in the entire 5×55 \times 5 array will be

S=4(a+b+c+d)+a1a+b1b+c1c+d1d S = 4(a+b+c+d) + a_1 \cdot a + b_1 \cdot b + c_1 \cdot c + d_1 \cdot d

If the first, the third and the fifth row contain the numbers x,yx, y, with xx denoting the number at the entry (1,1)(1,1), then the second and the fourth row will contain only the numbers z,tz, t, with zz denoting the number at the entry (2,1)(2,1). Then x1+y1=7x_1 + y_1 = 7 and x13x_1 \geqslant 3, y12y_1 \geqslant 2, z1+t1=2z_1 + t_1 = 2, and z1t1z_1 \geqslant t_1. Then {x1,y1}={5,2}\{x_1, y_1\} = \{5,2\} or {x1,y1}={4,3}\{x_1, y_1\} = \{4,3\}, respectively {z1,t1}={2,0}\{z_1, t_1\} = \{2,0\} or {z1,t1}={1,1}\{z_1, t_1\} = \{1,1\}. Then (a1,b1,c1,d1)(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,2,2,0),\ (5,2,1,1),\ (4,3,2,0),\ (4,3,1,1)

There are a total of 4!2!=12\frac{4!}{2!} = 12 permutations of (5,2,2,0)(5,2,2,0), also 1212 permutations of (5,2,1,1)(5,2,1,1), 2424 permutations of (4,3,2,0)(4,3,2,0) and finally, there are 1212 permutations of (4,3,1,1)(4,3,1,1). Hence, there are at most 6060 different possible total sums.

We can obtain indeed each of these 6060 combinations: take three rows ababa alternating with two rows cdcdccdc d c to get (5,2,2,0)(5,2,2,0); take three rows ababa alternating with one row cdcdccdc d c and a row (dcdcd)(d c d c d) to get (5,2,1,1)(5,2,1,1); take three rows ababca b a b c alternating with two rows cdcdac d c d a to get (4,3,2,0)(4,3,2,0); take three rows abcda alternating with two rows cdabcc d a b c to get (4,3,1,1)(4,3,1,1). By choosing for example a=103,b=102,c=10,d=1a=10^3, b=10^2, c=10, d=1, we can make all these sums different. Hence, 6060 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.