Track / Stage 5 / 374 of 400 #974 of 2000

Problem 974

AIME late

Combinatorics Difficulty 5.9 Prove it

6.3. In a $10 \times 10$ grid, each cell contains a positive integer. In each row, the largest number is circled (if there are multiple largest numbers, one of them is circled); in each column, the smallest number is circled (or one of the smallest numbers is circled). It is known that each circled number is circled twice. Prove: all numbers in the table are equal.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

6.3. First, prove that all the circled numbers are equal to each other. Use proof by contradiction.

Assume there are two circled numbers $a > b$ . Now consider the number $c$ that is in the same column as $a$ and the same row as $b$ . By the problem's condition, $a \leqslant c \leqslant b$ , which implies $a \leqslant b$ , a contradiction. Therefore, all the circled numbers are equal to each other.

Next, consider any number $x$ in the table. It is not greater than the largest number in the same row, nor is it less than the smallest number in the same column. However, from the previous proof, these two numbers are equal. Therefore, $x$ is also equal to them. This shows that all numbers in the table are equal.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.