In every cell of a square table is a number. The sum of the largest two numbers in each row
is and the sum of the largest two numbers in each column is b. Prove that .
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 , the size of the square table.
### Base Case:
For a table, let the entries be:
The sum of the largest two numbers in each row is:
The sum of the largest two numbers in each column is:
Since the sum of all entries in the table is the same for both rows and columns, we have:
### Inductive Step
Assume the statement holds for an table. We need to show it holds for an table.
Let be the largest entry in the table. Without loss of generality, assume is in the bottom left corner. We can shift rows and columns to place at position .
Let be the assertion that there exists another column with one of the largest two numbers in the first row, and be the assertion that there exists another row with one of the largest two numbers in the first column.
#### Case 1: Both and hold
The sum of the two largest numbers in row 1 is at least where is in row 1 and column . Thus, . Since is one of the largest two in column and the other number is at most , we get . Similarly, , so .
#### Case 2: does not hold
If does not hold, we are done by a symmetrical argument.
Note is at most the second largest number of row for any because for some . Since , .
Consider an alternate matrix . Initially, . For each that satisfies is one of the two largest numbers in column , say the two largest numbers are . Select such that , and reset to be . In column , the two largest numbers in is equal to . Also, this operation doesn't change the two largest numbers in each row of the matrix , so the sum of the two largest in each row is . We apply the inductive hypothesis on and to get , as needed.