Maths Olympiad Prep

Library / /19 of 19

Combinatorics Difficulty 8.0 National olympiad, round 2 Prove it North Macedonia

A 5×55 \times 5 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 2×22 \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.

Solutions — 2

Solution 1

We will prove that the maximum number of total sums is 6060.
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 RR be a row containing at least three of the numbers. Then, in row RR we can find three of the numbers in consecutive position, 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) \begin{pmatrix} \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{pmatrix}

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×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. \hfill (2)

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.(3) S = 4(a+b+c+d) + a_1 \cdot a + b_1 \cdot b + c_1 \cdot c + d_1 \cdot d. \qquad (3)

In 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 \ge 3, y12y_1 \ge 2, z1+t1=2z_1 + t_1 = 2, and z1t1z_1 \ge 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\}. (4)

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) (5,2,2,0),\ (5,2,1,1),\ (4,3,2,0),\ (4,3,1,1). \qquad (5)

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. (6)

We can obtain indeed each of these 6060 combinations: take three rows ababaababa alternating with two rows cdcdccdcdc to get (5,2,2,0)(5,2,2,0); take three rows ababaababa alternating with one row cdcdccdcdc and a row (dcdcd)(dcdcd) to get (5,2,1,1)(5,2,1,1); take three rows ababcababc alternating with two rows cdcdacdcda to get (4,3,2,0)(4,3,2,0); take three rows abcdaabcda alternating with two rows cdabccdabc to get (4,3,1,1)(4,3,1,1). (7)

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. (8)

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

Solution 2

Alternative version. Consider a regular table containing the four distinct numbers a,b,c,da, b, c, d. The four 2×22 \times 2 corners contain each all the four numbers, so that, if a1,b1,c1,d1a_1, b_1, c_1, d_1 are the numbers of appearances of a,b,ca, b, c and respectively dd in the middle row and column, then
S=4(a+b+c+d)+a1a+b1b+c1c+d1d.(1) S = 4(a+b+c+d) + a_1 \cdot a + b_1 \cdot b + c_1 \cdot c + d_1 \cdot d. \qquad (1')

Consider the numbers xx in position (3,3)(3,3), yy in position (3,2)(3,2), yy' in position (3,4)(3,4), zz in position (2,3)(2,3) and zz' in position (4,3)(4,3).
If zz=tz \neq z' = t, then y=yy = y', and in position (3,1)(3,1) and (3,5)(3,5) there will be the number xx. (2')

The second and fourth row can only contain now the numbers zz and tt, respectively the first and fifth row only xx and yy. (3')

Then x1+y1=7x_1 + y_1 = 7 and x13x_1 \ge 3, y12y_1 \ge 2, z1+t1=2z_1 + t_1 = 2, and z1t1z_1 \ge 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\}. (4')

One can continue now as in the first version.

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 and solution reproduced as published; topic and difficulty added by this site.