Maths Olympiad Prep

Library / /450 of 520

Combinatorics Difficulty 7.5 National olympiad, round 2 Prove it

In every cell of a square table is a number. The sum of the largest two numbers in each row
is aa and the sum of the largest two numbers in each column is b. Prove that a=ba = b.

Solution

To prove that the sum of the largest two numbers in each row is equal to the sum of the largest two numbers in each column, we will use induction on n n , the size of the n×n n \times n square table.

### Base Case: n=2 n = 2
For a 2×2 2 \times 2 table, let the entries be:
[a1,1a1,2a2,1a2,2] \begin{bmatrix} a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \end{bmatrix}

The sum of the largest two numbers in each row is:
a=max(a1,1,a1,2)+min(a1,1,a1,2)+max(a2,1,a2,2)+min(a2,1,a2,2) a = \max(a_{1,1}, a_{1,2}) + \min(a_{1,1}, a_{1,2}) + \max(a_{2,1}, a_{2,2}) + \min(a_{2,1}, a_{2,2})

The sum of the largest two numbers in each column is:
b=max(a1,1,a2,1)+min(a1,1,a2,1)+max(a1,2,a2,2)+min(a1,2,a2,2) b = \max(a_{1,1}, a_{2,1}) + \min(a_{1,1}, a_{2,1}) + \max(a_{1,2}, a_{2,2}) + \min(a_{1,2}, a_{2,2})

Since the sum of all entries in the table is the same for both rows and columns, we have:
a=b a = b

### Inductive Step
Assume the statement holds for an n×n n \times n table. We need to show it holds for an (n+1)×(n+1) (n+1) \times (n+1) table.

Let X X be the largest entry in the (n+1)×(n+1) (n+1) \times (n+1) table. Without loss of generality, assume X X is in the bottom left corner. We can shift rows and columns to place X X at position (n+1,1) (n+1, 1) .

Let C C be the assertion that there exists another column c1 c \neq 1 with one of the largest two numbers in the first row, and R R be the assertion that there exists another row r1 r \neq 1 with one of the largest two numbers in the first column.

#### Case 1: Both C C and R R hold
The sum of the two largest numbers in row 1 is at least X+t X + t where t t is in row 1 and column c c . Thus, aX+t a \geq X + t . Since t t is one of the largest two in column c c and the other number is at most X X , we get bX+ta b \leq X + t \leq a . Similarly, ba b \geq a , so b=a b = a .

#### Case 2: R R does not hold
If C C does not hold, we are done by a symmetrical argument.

Note a1,t a_{1,t} is at most the second largest number of row j j for any 2t,jn 2 \leq t, j \leq n because a=a1,1+a1,t=X+a1,t=aj,cj+aj,dj a = a_{1,1} + a_{1,t} = X + a_{1,t} = a_{j,c_j} + a_{j,d_j} for some cj,dj c_j, d_j . Since Xmax{aj,cj,aj,dj} X \geq \max\{a_{j,c_j}, a_{j,d_j}\} , a1,tmin{aj,cj,aj,dj} a_{1,t} \leq \min\{a_{j,c_j}, a_{j,d_j}\} .

Consider an alternate matrix (bi,j)2i,jn (b_{i,j})_{2 \leq i,j \leq n} . Initially, bi,j=ai,j b_{i,j} = a_{i,j} . For each t t that satisfies a1,t a_{1,t} is one of the two largest numbers in column t t , say the two largest numbers are a1,t,am,t a_{1,t}, a_{m,t} . Select 2jn 2 \leq j \leq n such that jm j \neq m , and reset bj,t b_{j,t} to be max{bj,t,a1,t} \max\{b_{j,t}, a_{1,t}\} . In column t t , the two largest numbers in (bi,j) (b_{i,j}) is equal to b b . Also, this operation doesn't change the two largest numbers in each row of the matrix (bi,j) (b_{i,j}) , so the sum of the two largest in each row is a a . We apply the inductive hypothesis on n1 n-1 and b b to get a=b a = b , as needed.

\blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.