A problem from the 2011 Moscow Mathematical Olympiad: In a certain square matrix, the sum of the two largest numbers in each row is r and the sum of the two largest in each column is c. Show that r = c.
|
SelectClick for Answer> |
Well, suppose otherwise. If r and c aren’t equal then one is larger; suppose r > c. Draw a circle around the largest number in each row and a square around the next largest. Each of the circled numbers is at least r/2 (because each is the largest in its row), so each must occupy a different column. Now consider the largest number with a square around it; call that x, and call the circled number in its column y. Let z be the number in y‘s row that has a square around it. Now y + z = r (because they’re the two marked numbers in a row) and y + x = c. Because the largest number with a square around it is x, x must be greater than or equal to z, but this is incompatible with our assumption that r > c. So the assumption is wrong and r and c must be equal.
From MIT mathematician Tanya Khovanova’s blog, via Peter Winkler’s Mathematical Puzzles, 2021.
|
