EGMO

Solution:

Answer: $\frac{2025}{89}$.
In general, if the table is $m^{2} \times m^{2}$, the answer is $\frac{m^{2}}{2m - 1}$.

The example is as follows: label rows and columns from $1$ to $m^{2}$, from top to bottom and left to right. For the first $m$ columns, write $\frac{1}{m}$ in all squares whose coordinates have the same residue modulo $m$ and place $0$ everywhere else. For the remaining $m^{2} - m$ columns, place $\frac{1}{m^{2}}$ everywhere. Then $R = m^{2} \cdot \frac{1}{m} = m$, and $C = m \cdot \frac{1}{m} + (m^{2} - m) \cdot \frac{1}{m^{2}} = 2 - \frac{1}{m}$. So the ratio is as claimed.

For each row, select one cell having the largest value appearing in said row and colour it red. Then, without loss of generality, we may rearrange the columns such that the red cells appear in the first $k$ columns from the left, and each column contains at least one red cell, for some $k \leq n$.

For the $j^{\mathrm{th}}$ column, for all $1 \leq j \leq k$, let $p_{j}$ and $n_{j}$ denote the sum and number of red cells in it, respectively. We observe that $c_{j}$, the biggest number in the $j^{\mathrm{th}}$ column, is at least $\frac{p_{j}}{n_{j}}$, for all $1 \leq j \leq k$. For all other columns, the largest value they contain is at least $\frac{1}{n}$, as their sum is $1$. Thus, $C \geq \frac{p_{1}}{n_{1}} + \frac{p_{2}}{n_{2}} + \dots + \frac{p_{k}}{n_{k}} + \frac{n - k}{n}$.

We can also observe that $R = p_{1} + p_{2} + \dots + p_{k}$.

Therefore we have to show that:
$$p_{1} + p_{2} + \dots +p_{k} \leq \frac{n}{2\sqrt{n} - 1} \cdot \left(\frac{p_{1}}{n_{1}} + \frac{p_{2}}{n_{2}} + \dots + \frac{p_{k}}{n_{k}} + \frac{n - k}{n}\right). \quad (*)$$
By construction, $n_{1} + n_{2} + \dots + n_{k} = n$, and, as the numbers in every column are nonnegative, we see that $p_{j} \leq 1$ for every $j$. Also, since each number in a red cell is at least $\frac{1}{n}$, we also have $p_{j} \geq \frac{n_{j}}{n}$.

Since our inequality is linear in each $p_{j}$, it suffices to prove it when each variable equals one of its two critical values. By relabeling, we may assume that $p_{j} = \frac{n_{j}}{n}$ for $1 \leq j \leq t$, and $p_{j} = 1$ for $t + 1 \leq j \leq k$, for an integer $0 \leq t \leq k$.

First, if $t = k$, we observe that $p_{1} + p_{2} + \dots +p_{k} = \frac{n_{1}}{n} + \frac{n_{2}}{n} + \dots + \frac{n_{k}}{n} = 1$, and that $\frac{p_{1}}{n_{1}} + \frac{p_{2}}{n_{2}} + \dots + \frac{p_{k}}{n_{k}} = \frac{k}{n}$, so the inequality becomes $1 \leq \frac{n}{2\sqrt{n} - 1}$, which is true.

From now on we may assume that $t < k$. We need to show that:
$$\frac{n_{1} + \dots + n_{t}}{n} +k - t \leq \frac{n}{2\sqrt{n} - 1} \cdot \left(\frac{t}{n} + \frac{1}{n_{t + 1}} + \dots + \frac{1}{n_{k}} + \frac{n - k}{n}\right).$$
By Cauchy-Schwarz inequality we have that:
$$\frac{1}{n_{t + 1}} + \dots + \frac{1}{n_{k}} \geq \frac{(k - t)^{2}}{n_{t + 1} + \dots + n_{k}} = \frac{(k - t)^{2}}{n - (n_{1} + \dots + n_{t})}. \quad (CS)$$
Let $n_{1} + \dots +n_{t} = n\cdot q$, where $0\leq q< 1$. Thus, it is now enough to show that:
$$q + k - t\leq \frac{n}{2\sqrt{n} - 1}\left(\frac{t}{n} +\frac{(k - t)^{2}}{n - nq} +\frac{n - k}{n}\right).$$
Let $k - t = \ell \geq 1$. The inequality becomes:
$$q + \ell \leq \frac{1}{2\sqrt{n} - 1}\cdot \left(n - \ell +\frac{\ell^{2}}{1 - q}\right).$$
Rearranging this we get:
$$n + q + \frac{\ell^{2}}{1 - q}\geq 2(q + \ell)\sqrt{n}.$$
If $q = 0$ the inequality is trivially true by $AM - GM$. Suppose now that $0< q< 1$. Then, by Cauchy-Schwarz, we have:
$$q + \frac{\ell^{2}}{1 - q} = \frac{q^{2}}{q} +\frac{\ell^{2}}{1 - q}\geq (q + \ell)^{2}.$$
It is therefore enough to show that $n + (q + \ell)^{2}\geq 2(q + \ell)\sqrt{n}$, which is true by $AM - GM$, completing the proof.

Solution 1'. We prove the main inequality $(\ast)$ in a slightly different manner. Instead of the strong lower bound $p_{j}\geq \frac{n_{j}}{n}$, we use the weaker, simpler and more immediate lower bound $p_{j}\geq 0$ (thus proving the inequality in a larger regime).
As in Solution 1, suppose $p_{j} = 0$ for $1\leq j\leq t$ and $p_{j} = 1$ for $t + 1\leq j\leq k$, with $\ell = k - t$. We also denote by $m = n_{t + 1} + \dots +n_{k}$ and note that $m\leq n - t$, since $n_{j}\geq 1$ for each $i\leq t$. We need to prove that:
$$\ell \leq \frac{n}{2\sqrt{n} - 1}\cdot \left(\frac{1}{n_{t + 1}} +\dots +\frac{1}{n_{k}} +\frac{n - k}{n}\right).$$
Rearranging and using the same Cauchy-Schwarz (CS) as in Solution 1, we see it suffices to show that:
$$(2\sqrt{n} -1)\ell \leq n - k + \frac{n\ell^{2}}{m},$$
or equivalently, that:
$$2\sqrt{n}\ell \leq n - t + \frac{n\ell^{2}}{m}.$$
But since $n - t\geq m$ this immediately follows from $2\sqrt{n}\ell \leq m + \frac{n\ell^{2}}{m}$, which is a simple application of $AM - GM$.

Solution 1". This is an alternative way of getting the upper bound on $\frac{R}{C}$ from
$$\frac{R}{C}\leq \frac{p_{1} + p_{2} + \ldots + p_{k}}{\frac{p_{1}}{n_{1}} + \frac{p_{2}}{n_{2}} + \ldots + \frac{p_{k}}{n_{k}} + \frac{n - k}{n}}.$$
Using the fact that $\sum_{j = 1}^{k}n_{j} = n$, we can rewrite the above right hand side as follows:
$$\frac{\sum_{j = 1}^{k}p_{j}}{\sum_{j = 1}^{k}\left(\frac{p_{j}}{n_{j}} +\frac{n_{j} - 1}{n}\right)}.$$
We notice that this is a quotient of affine functions in the $p_{j}$'s, for which the denominator does not vanish over the set defined by $0 \leq p_{j} \leq 1$. Therefore the maximum of this function is attained when a certain number of $p_{j}$'s are $1$ and the others are $0$. Without loss of generality we may assume that the first $t$ are equal to $1$ and the other $k - t$ are $0$ for some $0 \leq t \leq k$. Then one has that the previous expression is at most
$$\frac{t}{\sum_{1 \leq j \leq t} \left(\frac{1}{n_{j}} + \frac{n_{j} - 1}{n}\right) + \sum_{t < j \leq k} \frac{n_{j} - 1}{n}}.$$
We now lower bound the denominator by observing that the second sum is non negative, while each term of the first sum can be bounded by $AM - GM$ as follows:
$$\frac{1}{n_{j}} + \frac{n_{j} - 1}{n} \geq \frac{2}{\sqrt{n}} - \frac{1}{n}.$$
We therefore have
$$\frac{R}{C} \leq \max_{1 \leq t \leq k} \frac{t}{\sum_{1 \leq j \leq t} \left(\frac{2}{\sqrt{n}} - \frac{1}{n}\right)} = \frac{n}{2\sqrt{n} - 1},$$
which finishes the proof.

Solution $1^{\prime\prime}$. We follow the same notation as above. First, we apply Cauchy-Schwarz as follows :
$$\left(\sum_{i = 1}^{k} \frac{p_{i}}{n_{i}}\right) \left(\sum_{i = 1}^{k} p_{i} n_{i}\right) \geq \left(\sum_{i = 1}^{k} p_{i}\right)^{2} = R^{2}.$$
We now write $z_{i} = 1 - p_{i}$ for all $1 \leq i \leq k$, and observe that all $z_{i}$ are positive. Moreover, we have that $\sum_{i = 1}^{k} z_{i} = k - R$, and $\sum_{i = 1}^{k} p_{i} n_{i} = n - \sum_{i = 1}^{k} p_{i} z_{i}$. Thus, from our last inequality we get
$$\frac{p_{1}}{n_{1}} + \dots + \frac{p_{k}}{n_{k}} \geq \frac{R^{2}}{n - \sum_{i = 1}^{k} n_{i} z_{i}}.$$
As before we have $C \geq \frac{p_{1}}{n_{1}} + \dots + \frac{p_{k}}{n_{k}} + \frac{n - k}{n}$, and so
$$C \geq \frac{R^{2}}{n - \sum_{i = 1}^{k} n_{i} z_{i}} + \frac{n - k}{n} = \frac{R^{2}}{n - \sum_{i = 1}^{k} n_{i} z_{i}} + \frac{n - R - \sum_{i = 1}^{k} z_{i}}{n}.$$
Putting everything together we get
$$\frac{R}{C} \leq \frac{R}{\frac{R^{2}}{n - \sum_{i = 1}^{k} n_{i} z_{i}} + \frac{n - R - \sum_{i = 1}^{k} z_{i}}{n}} = \frac{n}{\frac{R n}{n - \sum_{i = 1}^{k} n_{i} z_{i}} + \frac{n - \sum_{i = 1}^{k} z_{i}}{R} - 1}.$$
Applying $AM - GM$ to the denominator we get $\frac{R}{C} \leq \frac{n}{2 \sqrt{n \frac{n - \sum_{i = 1}^{k} z_{i}}{n - \sum_{i = 1}^{k} n_{i} z_{i}} - 1}}$, which finishes the proof by noting that $\frac{n - \sum_{i = 1}^{k} z_{i}}{n - \sum_{i = 1}^{k} n_{i} z_{i}} \geq 1$.

Solution 2. This is an alternative approach that goes via an intermediary quantity in order to establish to the upper bound on $R / C$.
Let $x_{i j}$ be the entry in row $i$ and column $j$. Let $n = 2025$. The key idea is to analyze the expression:
$$T:= \sum_{i,j}x_{i j}\max \left(x_{i j},\frac{1}{n}\right).$$
On one hand, since $c_{j}\geq 1 / n$, we have $x_{i j}\max (x_{i j},\frac{1}{n})\leq x_{i j}c_{j}$ for every $(i,j)$. So
$$T\leq \sum_{j}\sum_{i}x_{i j}c_{j} = \sum_{j}c_{j} = C.$$
On the other hand, let $j_{i}$ be one of the indices for which $r_{i} = x_{i j_{i}}$. We therefore have:
$$T=\sum_{i}\left(x_{i j_{i}}\max \left(x_{i j_{i}},\frac{1}{n}\right)+\sum_{j\neq j_{i}}x_{i j}\max \left(x_{i j},\frac{1}{n}\right)\right)$$
$$\geq\sum_{i}\left(r_{i}^{2}+\frac{1}{n}\sum_{j\neq j_{i}}x_{i j}\right)$$
$$=\sum_{i}\left(r_{i}^{2}-\frac{1}{n}r_{i}+\frac{1}{n}\right)\geq\sum_{i}\left(\frac{2}{\sqrt{n}}r_{i}-\frac{1}{n}r_{i}\right)=\left(\frac{2}{\sqrt{n}}-\frac{1}{n}\right)R.$$
This gives the claimed result.