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 ri to be the largest value in row i, and let R=r1+r2+⋯+r2025. Similarly, define ci to be the largest value in column i, and let C=c1+c2+⋯+c2025. What is the largest possible value of CR?
What is the largest possible value of CR?
Solution
Solution:
Answer: 892025. In general, if the table is m2×m2, the answer is 2m−1m2.
The example is as follows: label rows and columns from 1 to m2, from top to bottom and left to right. For the first m columns, write m1 in all squares whose coordinates have the same residue modulo m and place 0 everywhere else. For the remaining m2−m columns, place m21 everywhere. Then R=m2⋅m1=m, and C=m⋅m1+(m2−m)⋅m21=2−m1. So the ratio is as claimed.
1/2
0
1/4
1/4
0
1/2
1/4
1/4
1/2
0
1/4
1/4
0
1/2
1/4
1/4
In particular, when n:=m2=2025, we get 892025. Now we need to show that CR≤2n−1n.
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≤n.
For the jth column, for all 1≤j≤k, let pj and nj denote the sum and number of red cells in it, respectively. We observe that cj, the biggest number in the jth column, is at least njpj, for all 1≤j≤k. For all other columns, the largest value they contain is at least n1, as their sum is 1. Thus, C≥n1p1+n2p2+⋯+nkpk+nn−k.
We can also observe that R=p1+p2+⋯+pk.
Therefore we have to show that: p1+p2+⋯+pk≤2n−1n⋅(n1p1+n2p2+⋯+nkpk+nn−k).(∗) By construction, n1+n2+⋯+nk=n, and, as the numbers in every column are nonnegative, we see that pj≤1 for every j. Also, since each number in a red cell is at least n1, we also have pj≥nnj.
Since our inequality is linear in each pj, it suffices to prove it when each variable equals one of its two critical values. By relabeling, we may assume that pj=nnj for 1≤j≤t, and pj=1 for t+1≤j≤k, for an integer 0≤t≤k.
First, if t=k, we observe that p1+p2+⋯+pk=nn1+nn2+⋯+nnk=1, and that n1p1+n2p2+⋯+nkpk=nk, so the inequality becomes 1≤2n−1n, which is true.
From now on we may assume that t<k. We need to show that: nn1+⋯+nt+k−t≤2n−1n⋅(nt+nt+11+⋯+nk1+nn−k). By Cauchy-Schwarz inequality we have that: nt+11+⋯+nk1≥nt+1+⋯+nk(k−t)2=n−(n1+⋯+nt)(k−t)2.(CS) Let n1+⋯+nt=n⋅q, where 0≤q<1. Thus, it is now enough to show that: q+k−t≤2n−1n(nt+n−nq(k−t)2+nn−k). Let k−t=ℓ≥1. The inequality becomes: q+ℓ≤2n−11⋅(n−ℓ+1−qℓ2). Rearranging this we get: n+q+1−qℓ2≥2(q+ℓ)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+1−qℓ2=qq2+1−qℓ2≥(q+ℓ)2. It is therefore enough to show that n+(q+ℓ)2≥2(q+ℓ)n, which is true by AM−GM, completing the proof.
Solution 1'. We prove the main inequality (∗) in a slightly different manner. Instead of the strong lower bound pj≥nnj, we use the weaker, simpler and more immediate lower bound pj≥0 (thus proving the inequality in a larger regime). As in Solution 1, suppose pj=0 for 1≤j≤t and pj=1 for t+1≤j≤k, with ℓ=k−t. We also denote by m=nt+1+⋯+nk and note that m≤n−t, since nj≥1 for each i≤t. We need to prove that: ℓ≤2n−1n⋅(nt+11+⋯+nk1+nn−k). Rearranging and using the same Cauchy-Schwarz (CS) as in Solution 1, we see it suffices to show that: (2n−1)ℓ≤n−k+mnℓ2, or equivalently, that: 2nℓ≤n−t+mnℓ2. But since n−t≥m this immediately follows from 2nℓ≤m+mnℓ2, which is a simple application of AM−GM.
Solution 1". This is an alternative way of getting the upper bound on CR from CR≤n1p1+n2p2+…+nkpk+nn−kp1+p2+…+pk. Using the fact that ∑j=1knj=n, we can rewrite the above right hand side as follows: ∑j=1k(njpj+nnj−1)∑j=1kpj. We notice that this is a quotient of affine functions in the pj's, for which the denominator does not vanish over the set defined by 0≤pj≤1. Therefore the maximum of this function is attained when a certain number of pj'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≤t≤k. Then one has that the previous expression is at most ∑1≤j≤t(nj1+nnj−1)+∑t<j≤knnj−1t. 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: nj1+nnj−1≥n2−n1. We therefore have CR≤1≤t≤kmax∑1≤j≤t(n2−n1)t=2n−1n, which finishes the proof.
Solution 1′′. We follow the same notation as above. First, we apply Cauchy-Schwarz as follows : (i=1∑knipi)(i=1∑kpini)≥(i=1∑kpi)2=R2. We now write zi=1−pi for all 1≤i≤k, and observe that all zi are positive. Moreover, we have that ∑i=1kzi=k−R, and ∑i=1kpini=n−∑i=1kpizi. Thus, from our last inequality we get n1p1+⋯+nkpk≥n−∑i=1kniziR2. As before we have C≥n1p1+⋯+nkpk+nn−k, and so C≥n−∑i=1kniziR2+nn−k=n−∑i=1kniziR2+nn−R−∑i=1kzi. Putting everything together we get CR≤n−∑i=1kniziR2+nn−R−∑i=1kziR=n−∑i=1kniziRn+Rn−∑i=1kzi−1n. Applying AM−GM to the denominator we get CR≤2nn−∑i=1knizin−∑i=1kzi−1n, which finishes the proof by noting that n−∑i=1knizin−∑i=1kzi≥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 xij be the entry in row i and column j. Let n=2025. The key idea is to analyze the expression: T:=i,j∑xijmax(xij,n1). On one hand, since cj≥1/n, we have xijmax(xij,n1)≤xijcj for every (i,j). So T≤j∑i∑xijcj=j∑cj=C. On the other hand, let ji be one of the indices for which ri=xiji. We therefore have: T=i∑xijimax(xiji,n1)+j=ji∑xijmax(xij,n1) ≥i∑ri2+n1j=ji∑xij =i∑(ri2−n1ri+n1)≥i∑(n2ri−n1ri)=(n2−n1)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.