Maths Olympiad Prep

Library / /21 of 25

Algebra Difficulty 8.0 Shortlist Prove it European Girls' Mathematical Olympiad (EGMO)

Problem:

In each cell of a 2025×20252025 \times 2025 board, a nonnegative real number is written in such a way that the sum of the numbers in each row is equal to 11, and the sum of the numbers in each column is equal to 11. Define rir_{i} to be the largest value in row ii, and let R=r1+r2++r2025R = r_{1} + r_{2} + \dots + r_{2025}. Similarly, define cic_{i} to be the largest value in column ii, and let C=c1+c2++c2025C = c_{1} + c_{2} + \dots + c_{2025}. What is the largest possible value of RC\frac{R}{C}?

What is the largest possible value of RC\frac{R}{C}?

Solution

Solution:

Answer: 202589\frac{2025}{89}.
In general, if the table is m2×m2m^{2} \times m^{2}, the answer is m22m1\frac{m^{2}}{2m - 1}.

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

1/201/41/4
01/21/41/4
1/201/41/4
01/21/41/4

In particular, when n:=m2=2025n := m^{2} = 2025, we get 202589\frac{2025}{89}. Now we need to show that RCn2n1\frac{R}{C} \leq \frac{n}{2\sqrt{n} - 1}.

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 kk columns from the left, and each column contains at least one red cell, for some knk \leq n.

For the jthj^{\mathrm{th}} column, for all 1jk1 \leq j \leq k, let pjp_{j} and njn_{j} denote the sum and number of red cells in it, respectively. We observe that cjc_{j}, the biggest number in the jthj^{\mathrm{th}} column, is at least pjnj\frac{p_{j}}{n_{j}}, for all 1jk1 \leq j \leq k. For all other columns, the largest value they contain is at least 1n\frac{1}{n}, as their sum is 11. Thus, Cp1n1+p2n2++pknk+nknC \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=p1+p2++pkR = p_{1} + p_{2} + \dots + p_{k}.

Therefore we have to show that:
p1+p2++pkn2n1(p1n1+p2n2++pknk+nkn).() 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, n1+n2++nk=nn_{1} + n_{2} + \dots + n_{k} = n, and, as the numbers in every column are nonnegative, we see that pj1p_{j} \leq 1 for every jj. Also, since each number in a red cell is at least 1n\frac{1}{n}, we also have pjnjnp_{j} \geq \frac{n_{j}}{n}.

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

First, if t=kt = k, we observe that p1+p2++pk=n1n+n2n++nkn=1p_{1} + p_{2} + \dots +p_{k} = \frac{n_{1}}{n} + \frac{n_{2}}{n} + \dots + \frac{n_{k}}{n} = 1, and that p1n1+p2n2++pknk=kn\frac{p_{1}}{n_{1}} + \frac{p_{2}}{n_{2}} + \dots + \frac{p_{k}}{n_{k}} = \frac{k}{n}, so the inequality becomes 1n2n11 \leq \frac{n}{2\sqrt{n} - 1}, which is true.

From now on we may assume that t<kt < k. We need to show that:
n1++ntn+ktn2n1(tn+1nt+1++1nk+nkn). \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:
1nt+1++1nk(kt)2nt+1++nk=(kt)2n(n1++nt).(CS) \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 n1++nt=nqn_{1} + \dots +n_{t} = n\cdot q, where 0q<10\leq q< 1. Thus, it is now enough to show that:
q+ktn2n1(tn+(kt)2nnq+nkn). 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 kt=1k - t = \ell \geq 1. The inequality becomes:
q+12n1(n+21q). 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+21q2(q+)n. n + q + \frac{\ell^{2}}{1 - q}\geq 2(q + \ell)\sqrt{n}.
If q=0q = 0 the inequality is trivially true by AMGMAM - GM. Suppose now that 0<q<10< q< 1. Then, by Cauchy-Schwarz, we have:
q+21q=q2q+21q(q+)2. 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+)22(q+)nn + (q + \ell)^{2}\geq 2(q + \ell)\sqrt{n}, which is true by AMGMAM - GM, completing the proof.

Solution 1'. We prove the main inequality ()(\ast) in a slightly different manner. Instead of the strong lower bound pjnjnp_{j}\geq \frac{n_{j}}{n}, we use the weaker, simpler and more immediate lower bound pj0p_{j}\geq 0 (thus proving the inequality in a larger regime).
As in Solution 1, suppose pj=0p_{j} = 0 for 1jt1\leq j\leq t and pj=1p_{j} = 1 for t+1jkt + 1\leq j\leq k, with =kt\ell = k - t. We also denote by m=nt+1++nkm = n_{t + 1} + \dots +n_{k} and note that mntm\leq n - t, since nj1n_{j}\geq 1 for each iti\leq t. We need to prove that:
n2n1(1nt+1++1nk+nkn). \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:
(2n1)nk+n2m, (2\sqrt{n} -1)\ell \leq n - k + \frac{n\ell^{2}}{m},
or equivalently, that:
2nnt+n2m. 2\sqrt{n}\ell \leq n - t + \frac{n\ell^{2}}{m}.
But since ntmn - t\geq m this immediately follows from 2nm+n2m2\sqrt{n}\ell \leq m + \frac{n\ell^{2}}{m}, which is a simple application of AMGMAM - GM.

Solution 1". This is an alternative way of getting the upper bound on RC\frac{R}{C} from
RCp1+p2++pkp1n1+p2n2++pknk+nkn. \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 j=1knj=n\sum_{j = 1}^{k}n_{j} = n, we can rewrite the above right hand side as follows:
j=1kpjj=1k(pjnj+nj1n). \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 pjp_{j}'s, for which the denominator does not vanish over the set defined by 0pj10 \leq p_{j} \leq 1. Therefore the maximum of this function is attained when a certain number of pjp_{j}'s are 11 and the others are 00. Without loss of generality we may assume that the first tt are equal to 11 and the other ktk - t are 00 for some 0tk0 \leq t \leq k. Then one has that the previous expression is at most
t1jt(1nj+nj1n)+t<jknj1n. \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 AMGMAM - GM as follows:
1nj+nj1n2n1n. \frac{1}{n_{j}} + \frac{n_{j} - 1}{n} \geq \frac{2}{\sqrt{n}} - \frac{1}{n}.
We therefore have
RCmax1tkt1jt(2n1n)=n2n1, \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 11^{\prime\prime}. We follow the same notation as above. First, we apply Cauchy-Schwarz as follows :
(i=1kpini)(i=1kpini)(i=1kpi)2=R2. \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 zi=1piz_{i} = 1 - p_{i} for all 1ik1 \leq i \leq k, and observe that all ziz_{i} are positive. Moreover, we have that i=1kzi=kR\sum_{i = 1}^{k} z_{i} = k - R, and i=1kpini=ni=1kpizi\sum_{i = 1}^{k} p_{i} n_{i} = n - \sum_{i = 1}^{k} p_{i} z_{i}. Thus, from our last inequality we get
p1n1++pknkR2ni=1knizi. \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 Cp1n1++pknk+nknC \geq \frac{p_{1}}{n_{1}} + \dots + \frac{p_{k}}{n_{k}} + \frac{n - k}{n}, and so
CR2ni=1knizi+nkn=R2ni=1knizi+nRi=1kzin. 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
RCRR2ni=1knizi+nRi=1kzin=nRnni=1knizi+ni=1kziR1. \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 AMGMAM - GM to the denominator we get RCn2nni=1kzini=1knizi1\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 ni=1kzini=1knizi1\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/CR / C.
Let xijx_{i j} be the entry in row ii and column jj. Let n=2025n = 2025. The key idea is to analyze the expression:
T:=i,jxijmax(xij,1n). T:= \sum_{i,j}x_{i j}\max \left(x_{i j},\frac{1}{n}\right).
On one hand, since cj1/nc_{j}\geq 1 / n, we have xijmax(xij,1n)xijcjx_{i j}\max (x_{i j},\frac{1}{n})\leq x_{i j}c_{j} for every (i,j)(i,j). So
Tjixijcj=jcj=C. T\leq \sum_{j}\sum_{i}x_{i j}c_{j} = \sum_{j}c_{j} = C.
On the other hand, let jij_{i} be one of the indices for which ri=xijir_{i} = x_{i j_{i}}. We therefore have:
T=i(xijimax(xiji,1n)+jjixijmax(xij,1n)) 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)
i(ri2+1njjixij) \geq\sum_{i}\left(r_{i}^{2}+\frac{1}{n}\sum_{j\neq j_{i}}x_{i j}\right)
=i(ri21nri+1n)i(2nri1nri)=(2n1n)R. =\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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.