Maths Olympiad Prep

Library / Mongolian Mathematical Olympiad /91 of 97

Mongolian Mathematical Olympiad

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 1≤i,j≤51 \leq i, j \leq 5. Initially, ai,j=5(i−1)+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,j′a_{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=K−ai,j r_i + c_j = K - a_{i,j}

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

This means the sequence c1,c2,…,c5c_1, c_2, \dots, c_5 must satisfy cj−ck=j−kc_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=K−ai,j r_i + c_j = K - a_{i,j}
rk+cj=K−ak,j r_k + c_j = K - a_{k,j}
Subtract:
ri−rk=ak,j−ai,j r_i - r_k = a_{k,j} - a_{i,j}
But ak,j−ai,j=5(k−i)a_{k,j} - a_{i,j} = 5(k-i).
So ri−rk=5(k−i)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=K−ai,j r_i + c_j = K - a_{i,j}
But ai,j=5(i−1)+ja_{i,j} = 5(i-1) + j, so
ri+cj=K−(5(i−1)+j) r_i + c_j = K - (5(i-1) + j)
(5i+e)+(j+d)=K−5(i−1)−j (5i + e) + (j + d) = K - 5(i-1) - j
5i+e+j+d=K−5i+5−j 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: K−5(i−1)−jK - 5(i-1) - j

Bring all terms to one side:
5i+e+j+d+5(i−1)+j−K=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=K−ai,jr_i + c_j = K - a_{i,j}:
5i+e+j+d=K−(5(i−1)+j) 5i + e + j + d = K - (5(i-1) + j)
5i+e+j+d=K−5i+5−j 5i + e + j + d = K - 5i + 5 - j
5i+e+j+d+5i+j−K−5=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: K−5(i−1)−jK - 5(i-1) - j

So:
5i+e+j+d=K−5(i−1)−j 5i + e + j + d = K - 5(i-1) - j
5i+e+j+d+5(i−1)+j−K=0 5i + e + j + d + 5(i-1) + j - K = 0
5i+e+j+d+5i−5+j−K=0 5i + e + j + d + 5i - 5 + j - K = 0
10i+e+d+2j−5−K=0 10i + e + d + 2j - 5 - K = 0
K=10i+e+d+2j−5 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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.