Let $m,n\in\mathbb Z_{\ge 0},$ $a_0,a_1,\ldots ,a_m,b_0,b_1,\ldots ,b_n\in\mathbb R_{\ge 0}$ For any integer $0\le k\le m+n,$ define $c_k:=\max_{i+j=k}a_ib_j.$ Proof $$\frac 1{m+n+1}\sum_{k=0}^{m+n}c_k\ge\frac 1{(m+1)(n+1)}\sum_{i=0}^{m}a_i\sum_{j=0}^{n}b_j.$$ Created by Yinghua Ai
Problem
Source: 2024 CTST P18
Tags: 2024 CTST, inequalities, conbinatorics
25.03.2024 07:52
Related problems should be 2017 Polish Final P6 and 2003 IMO SL A6.
25.03.2024 11:34
Also related to this problem.But I don't think it's possible to apply the methods mentioned above to this problem.
27.03.2024 16:03
Is this a discrete form of Prekopa-Leindler Inequality?
28.03.2024 15:56
I roared for 4 hrs and finally made it to the weaker version of m=n... I'm so vegetable 我嚎了4个小时才整出来m=n的弱化情况…… 我太菜了
28.03.2024 16:59
5th hr: okay if m-n is odd 第五个小时写出来m和n差为奇数时的情况
28.03.2024 17:06
though I've managed it out,but it's quite lengthy
28.03.2024 17:38
It sure is difficult
29.03.2024 06:09
wrong $~~~$
29.03.2024 06:17
Indeed, this problem has nothing to do with Prekopa-Leindler Inequality, and every solution I have seen so far which applies integral turns out to be a fake solve. Try to see this as a combinatorics problem.
29.03.2024 10:04
Rushery_10 wrote: Indeed, this problem has nothing to do with Prekopa-Leindler Inequality, and every solution I have seen so far which applies integral turns out to be a fake solve. Try to see this as a combinatorics problem. Yep,I've been doing it in another way
30.03.2024 15:54
The clever solution by contestant TJF: Induct on $m+n$: If $m=0$ or $n=0$, obvious. Suppose correct when $m+n-1$, and consider $m,n\ge1$. Let $A=\sum_{i=0}^{m}a_i,B=\sum_{j=0}^{n}b_j$. By IH, $\sum_{k=1}^{m+n}c_k\ge\frac{m+n}{m(n+1)}\sum_{i=1}^{m}a_i\sum_{j=0}^{n}b_j=\frac{m+n}{m(n+1)}(A-a_0)B$ $\sum_{k=1}^{m+n}c_k\ge\frac{m+n}{(m+1)n}\sum_{i=0}^{m}a_i\sum_{j=1}^{n}b_j=\frac{m+n}{(m+1)n}A(B-b_0)$. It suffices to prove that $a_0b_0+\max\left(\frac{m+n}{m(n+1)}(A-a_0)B,\frac{m+n}{(m+1)n}A(B-b_0)\right)\ge\frac{(m+n+1)AB}{(m+1)(n+1)}$. For simplicity, denote $x=\frac{a_0}A,y=\frac{b_0}B$. It suffices to prove that $(m+1)(n+1)xy+(m+n)\max\left(\frac{m+1}m(1-x),\frac{n+1}{n}(1-y)\right)\ge m+n+1$. Let $t=\max\left(\frac{m+1}m(1-x),\frac{n+1}{n}(1-y)\right)$. $x\ge1-\frac{mt}{m+1},y\ge1-\frac{nt}{n+1}$. It suffices to prove that $(m+1-mt)(n+1-nt)+(m+n)t\ge m+n+1$. But that's just $mn(t-1)^2\ge0$. $\Box$