Европейская математическая олимпиада среди девочек (EGMO). 2025 год. Косово

В каждой клетке таблицы $2025 \times 2025$ записано неотрицательное вещественное число так, что сумма чисел в каждой строке равна $1$, и сумма чисел в каждом столбце также равна $1$. Обозначим через $r_i$ наибольшее число в строке с номером $i$, и через $R = r_1 + r_2 + \dots + r_{2025}$. Обозначим через $c_i$ наибольшее число в столбце с номером $i$, и через $C = c_1 + c_2 + \dots + c_{2025}$. Найдите наибольшее возможное значение выражения $\frac{R}{C}$.

Комментарий/решение

Сложность задачи в том, что таблица это не единственный квадрат из условия :/

В первых 45 строках первого столбца поставим $\frac{1}{45}$, в остальных ноль. Далее, с 46 по 90 строку второго столбца поставим $\frac{1}{45}$, в остальных ноль. И так далее до 45 столбца, где мы ставим $\frac{1}{45}$ в строках от 1981 до 2025. Во всех остальных столбцах таблицы ставим $\frac{1}{2025}$. Несложно понять, что $R = 45$ и $C = 1 + \frac{1980}{2025} = \frac{89}{2025}R$

Для оценки просто подгоняем все неравенства под ситуацию в примере. Переставим столбцы и строки так, чтобы в первых $d_1$ строках наибольшее число было в первом столбце, в следующих $d_2$ строках было во втором столбце, продолжая так же до $d_k$ строк с наибольшим числом в $k$-ом столбце. При этом, $d_1+\ldots+d_k = 2025$ и $k \le 2025$.

Оценим $C$ снизу, как $r_{max_1} + \ldots + r_{max_k} + (2025-k) \cdot \frac{1}{2025}$, где $r_{max_i}$ это максимальное из $r_{d_1 + \ldots + d_{i-1}+1}$, $\ldots$ ,$r_{d_1 + \ldots + d_{i}}$. Теперь подберемся ближе к общей сумме, оценивая $r_{max_i} \ge \frac{r_{d_1 + \ldots + d_{i-1}+1} + \ldots + r_{d_1 + \ldots + d_{i}}}{d_i} = \frac{S_i}{d_i}$.

Выходит $C \ge \frac{S_1}{d_1} + \ldots + \frac{S_k}{d_k} + (2025-k)\cdot \frac{1}{2025}$.

$R = S_1 + \ldots + S_k$, поэтому мы хотим суммировать числители у предыдущего выражения, поэтому мы делаем следующую оценку: $\frac{S_1^2}{S_1d_1} + \ldots + \frac{S_k^2}{S_kd_k} + (2025-k)\cdot \frac{1}{2025} \ge \frac{(S_1+\ldots + S_k)^2}{S_1d_1 + \ldots + S_kd_k} + \frac{2025-k}{2025}$.

$S_i \le 1$, откуда можно получить, что знаменатель $\le 2025$, что приведет к (в большинстве случаев) слабой оценке, но можно поступить умнее: $$S_1d_1 + \ldots + S_kd_k = d_1 + \ldots + d_k - (1-S_1)d_1 - \ldots - (1-S_k)d_k \le 2025 - (k - R).$$

Теперь, $C \ge \frac{R^2}{2025 - k + R} + \frac{2025-k+R}{2025} - \frac{R}{2025} \ge 2 \cdot \frac{R}{45} - \frac{R}{2025} = \frac{89R}{2025}$.