Maths Olympiad Prep

Library / /64 of 69

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Mongolia

The numbers 1,2,,251, 2, \dots, 25 are written in the cells of a 5×55 \times 5 grid as shown below.
Figure 1
Is it possible to make all the numbers in the grid equal by performing a series of operations, where each operation consists of selecting either a row or a column and increasing all the numbers in that row or column by 1?

Solution

Let us denote the cell in row ii and column jj by ai,ja_{i,j}, where 1i,j51 \leq i, j \leq 5. Initially, ai,j=5(i1)+ja_{i,j} = 5(i-1) + j.

Each operation increases all numbers in a row or a column by 11. Suppose we perform rir_i operations on row ii and cjc_j operations on column jj. Then the final value in cell (i,j)(i, j) is:

ai,j=ai,j+ri+cj a_{i,j}' = a_{i,j} + r_i + c_j

We want all ai,ja_{i,j}' to be equal. That is, for all i,ji, j:

ai,j+ri+cj=K a_{i,j} + r_i + c_j = K
for some constant KK.

Rewriting:
ri+cj=Kai,j r_i + c_j = K - a_{i,j}

Consider two cells in the same row ii, columns jj and kk:
ri+cj=Kai,j r_i + c_j = K - a_{i,j}
ri+ck=Kai,k r_i + c_k = K - a_{i,k}
Subtract:
cjck=ai,kai,j c_j - c_k = a_{i,k} - a_{i,j}
But ai,kai,j=kja_{i,k} - a_{i,j} = k - j (since ai,j=5(i1)+ja_{i,j} = 5(i-1) + j).
So cjck=kjc_j - c_k = k - j.

This means the sequence c1,c2,,c5c_1, c_2, \dots, c_5 must satisfy cjck=jkc_j - c_k = j - k for all j,kj, k. This is only possible if cj=j+dc_j = j + d for some constant dd.

Similarly, consider two cells in the same column jj, rows ii and kk:
ri+cj=Kai,j r_i + c_j = K - a_{i,j}
rk+cj=Kak,j r_k + c_j = K - a_{k,j}
Subtract:
rirk=ak,jai,j r_i - r_k = a_{k,j} - a_{i,j}
But ak,jai,j=5(ki)a_{k,j} - a_{i,j} = 5(k-i).
So rirk=5(ki)r_i - r_k = 5(k-i), so ri=5i+er_i = 5i + e for some constant ee.

Now, plug cj=j+dc_j = j + d and ri=5i+er_i = 5i + e into the equation:
ri+cj=Kai,j r_i + c_j = K - a_{i,j}
But ai,j=5(i1)+ja_{i,j} = 5(i-1) + j, so
ri+cj=K(5(i1)+j) r_i + c_j = K - (5(i-1) + j)
(5i+e)+(j+d)=K5(i1)j (5i + e) + (j + d) = K - 5(i-1) - j
5i+e+j+d=K5i+5j 5i + e + j + d = K - 5i + 5 - j
5i+j+e+d+5i+j=K+5 5i + j + e + d + 5i + j = K + 5
Wait, this is inconsistent. Let's simplify:

Left: 5i+e+j+d5i + e + j + d
Right: K5(i1)jK - 5(i-1) - j

Bring all terms to one side:
5i+e+j+d+5(i1)+jK=0 5i + e + j + d + 5(i-1) + j - K = 0
But this is not matching. Let's try plugging ri=5i+er_i = 5i + e, cj=j+dc_j = j + d into ri+cj=Kai,jr_i + c_j = K - a_{i,j}:
5i+e+j+d=K(5(i1)+j) 5i + e + j + d = K - (5(i-1) + j)
5i+e+j+d=K5i+5j 5i + e + j + d = K - 5i + 5 - j
5i+e+j+d+5i+jK5=0 5i + e + j + d + 5i + j - K - 5 = 0
Wait, this is not matching. Let's try to solve for KK:

Left: 5i+e+j+d5i + e + j + d
Right: K5(i1)jK - 5(i-1) - j

So:
5i+e+j+d=K5(i1)j 5i + e + j + d = K - 5(i-1) - j
5i+e+j+d+5(i1)+jK=0 5i + e + j + d + 5(i-1) + j - K = 0
5i+e+j+d+5i5+jK=0 5i + e + j + d + 5i - 5 + j - K = 0
10i+e+d+2j5K=0 10i + e + d + 2j - 5 - K = 0
K=10i+e+d+2j5 K = 10i + e + d + 2j - 5
But KK must be constant for all i,ji, j, which is only possible if the coefficients of ii and jj are zero, i.e., 10i+2j10i + 2j must be constant, which is impossible as ii and jj vary.

Therefore, it is not possible to make all the numbers in the grid equal by performing such operations.

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.