14th European Girls' Mathematical Olympiad (EGMO 2025)

Problem 6 In each cell of a 2025 × 2025 board, a nonnegative real number is written in such a way that the sum of the numbers in each row is equal to 1, and the sum of the numbers in each column is equal to 1. Define r_i to be the largest value in row i, and let R = r₁ + r₂ + · · · + r₂₀₂₅. Similarly, define ci to be the largest value in column i, and let C = c₁ + c₂ + · · · + c₂₀₂₅. What is the largest possible value of $\frac{R}{C}$ ?

SOLUTION

The largest possible value of $\frac RC$ is $\frac{2025}{89}$ . For the construction, partition the left $45$ columns into $45\times45$ squares, and put $\frac1{45}$ in each of the main diagonals of the squares and $0$ s elsewhere in those squares. Fill the rest of the board with $\frac1{2025}$ . Then, $R=45$ and $C=1+\frac{1980}{2025}=\frac{89}{45}$ , so $\frac RC=\frac{2025}{89}$ .

Now, we show $\frac RC\leq\frac{2025}{89}$ . For each row, circle the largest number in the row. Then, let $a_i$ be the number of circles in column $i$ and let $s_i$ be the sum of the circles in column $i$ . Then, we can pick $C\geq\sum_{a_i>0}\left(\frac{s_i}{a_i}-\frac1{2025}\right)+1$ . By AM-GM, $\frac{s_i}{a_i}\geq-\frac1{2025}a_i+\frac2{45}\sqrt{s_i}$ , so
$\begin{align*} C&\geq\sum_{a_i>0}\left(-\frac1{2025}a_i+\frac2{45}\sqrt{s_i}-\frac1{2025}\right)+1\\ &=\sum_{a_i>0}\left(\frac2{45}\sqrt{s_i}-\frac1{2025}\right)\\ &\geq\sum_{a_i>0}\frac{89}{2025}s_i\\ &=\frac{89}{2025}R, \end{align*}$
as $\frac2{45}\sqrt{s_i}-\frac1{2025}\geq\frac{89}{2025}s_i$ is equivalent to $(\sqrt{s_i}-1)(89\sqrt{s_i}-1)\leq0$ since each circled number must be at least $\frac1{2025}$ . Therefore, $\frac RC\leq\frac{2025}{89}$ .