Given integer $n\geq 2$. Find the minimum value of $\lambda {}$, satisfy that for any real numbers $a_1$, $a_2$, $\cdots$, ${a_n}$ and ${b}$, $$\lambda\sum\limits_{i=1}^n\sqrt{|a_i-b|}+\sqrt{n\left|\sum\limits_{i=1}^na_i\right|}\geqslant\sum\limits_{i=1}^n\sqrt{|a_i|}.$$
Problem
Source: 2023 China TST Problem 21
Tags: inequalities
01.04.2023 08:10
the answer should be (n-1+sqrt(n-1)/sqrtn.However I can't prove it...
03.04.2023 01:25
06.04.2023 06:10
Here is a smoothing solution. The answer is $\frac{n-1+\sqrt{n-1}}{\sqrt{n}}$. The construction is $(a_1,\cdots,a_n)=(1,\cdots,1,-(n-1))$ and $b=1$. Step 1: We may assume $\sum a_j = 0$. Proof: I will maximize $$ f(c) = \sum\limits_{i=1}^n\sqrt{|a_i+c|} - \sqrt{n\left|\sum\limits_{i=1}^n (a_i+c)\right|}$$ Replace $a_j$ with $a_j-\mu$ such that $\sum a_j=0$ (when I shift, this step can often give great intuition). Then $$f(c) = \sum\limits_{i=1}^n(\sqrt{|a_i+c|} - \sqrt{|c|}) \le \sum\limits_{i=1}^n\sqrt{|a_i|} = f(0)$$ Hence the problem becomes as follows: Given real numbers $a_1,\cdots,a_n$ where $a_1+\cdots+a_n=0$, maximize $$\frac{\sum_{j=1}^n \sqrt{|a_j|}}{\sum_{j=1}^n \sqrt{|a_j-b|}}$$ Over all $b\in \mathbb{R}$. Step 2: If $b$ minimizes $\sum\limits_{j=1}^n \sqrt{|a_j-b|}$ then $b=a_j$ for some $j$. Proof: Note $f(b) = \sqrt{|x-b|}$ is concave so $\sum\limits_{j=1}^n \sqrt{|a_j-b|}$ is also concave. Therefore the minimum must hold at a point where the derivative is not defined. When $n=2$ the answer is obviously $\sqrt{2}$. Henceforth assume $n\ge 3$ and $\lambda \ge \frac{2+\sqrt{2}}{\sqrt{3}}$. WLOG $b=a_n$. Hence we have reduced the problem to as follows: Given real numbers $a_1,\cdots,a_{n-1},b$ where $a_1+\cdots+a_{n-1}+b=0$, maximize $$\frac{\sum_{j=1}^{n-1} \sqrt{|a_j|} + \sqrt{|b|}}{\sum_{j=1}^{n-1} \sqrt{|a_j-b|}}$$ Fix $b=1, a_1,\cdots,a_{n-1}$, and suppose $$\sum_{j=1}^n \sqrt{|a_j|} +1 = \lambda \left(\sum_{j=1}^n \sqrt{|a_j-1|}\right)$$ Let $$f(a_1,\cdots,a_{n-1}) = \sum_{j=1}^n \sqrt{|a_j|} +1 -\lambda \left(\sum_{j=1}^n \sqrt{|a_j-1|}\right), h(x) = \sqrt{|x|} - \lambda \sqrt{|x-1|}$$We wish to maximize $f(a_1,\cdots,a_{n-1})$ subject to the constraint $g(a_1,\cdots,a_{n-1})=a_1+\cdots+a_{n-1}=-1$, and see when the max is 0 (i.e. $\lambda$ is maximized). We can see, when $a_j > 100(n-1)+1$ for some $j$, then there exists $k$ such that $a_k < -100$ (WLOG, $|a_j| > |a_k|$). This implies that if change $(a_j, a_k)$ to $(a_j-\epsilon, a_k+\epsilon)$, $f$ would decrease; it would change by $\epsilon (1+o(1)) \frac 12 (a_j^{-1/2} - \lambda (a_j-1)^{-1/2} + |a_k|^{-1/2} -\lambda |a_k+1|^{-1/2}) < 0 $ Where the $o(1)$ term represents the error term which is a function that tends to $0$ as $\epsilon$ tends to $0$. Therefore, the maximum $\lambda$ holds when $|a_1|, \cdots, |a_{n-1}| \le 100$, i.e. $(a_1,\cdots,a_{n-1}) \in [-100,100]^{n-1}$. Note $[-100,100]^{n-1} \in \mathbb{R}^{n-1}$ is compact, so by sharpness principle, the maximum of $f$ exists, and we know it does not exist on the boundary of $[-100,100]^{n-1}$, so it exists in an interior point. Since the gradient of the constraint function (symbolically $\nabla g$ ) is always $\langle 1,\cdots,1\rangle$ is nonzero, we can see that $\nabla f = t\nabla g = \langle t,\cdots, t\rangle $ for some $t\in \mathbb{R}$ (whenever $\nabla f$ is defined; we do have, for all $a_j\notin \{0,1\}$, $\partial f/\partial a_j$ must be equal, and we can focus on the set of $a_j$ that is not equal to 1, since any $a_j$ cannot be 0). We know that $$\frac{\partial f}{\partial a_j} = \frac 12 ( \text{sgn}(a_j) |a_j|^{-1/2} - \lambda \text{sgn}(a_j-1) |a_j-1|^{-1/2}) = t \qquad \forall j \text{ such that } a_j\ne 1 $$ There exists $a_j$ such that $a_j\le -1$. We also know that $h'(x) > \frac{\lambda}{2} > h'(y)$ for all $x\in (0,1), y\in (-\infty,0)$ hence none of the $a_j$'s are in $(0,1)$ If there exists $j,k$ such that $a_j>1$ and $a_k>1$, then $\frac{\partial^2 f}{(\partial a_j)^2} = -\frac 14 (a_j^{-3/2} - \lambda (a_j-1)^{-3/2} ) > 0$ so replacing $(a_j,a_k)$ by $(a_j-\epsilon, a_k+\epsilon)$ does increase $f$ as long as $a_j-\epsilon, a_k+\epsilon \ge 1$. Thus we can assume one of $a_j,a_k$ is 1. If there exists $j,k$ such that $a_j\le 0$ and $a_k\le 0$ we prove $$h(a_j)+h(a_k) \le h(1) + h(a_j+a_k-1) $$ $$\iff \sqrt{|a_j|} + \sqrt{|a_k|} - \lambda \sqrt{|a_j-1|} - \lambda \sqrt{|a_k-1|} - 1 - \sqrt{|a_j+a_k-1|} + \lambda \sqrt{|a_j+a_k-2|} \le 0 $$ Note that $\sqrt{x+1}+\sqrt{y+1}-\sqrt{x+y+2} \ge \sqrt{x}+\sqrt{y}-\sqrt{x+y}$ for all $x,y \in \mathbb{R}_{\ge 0}$ so we are done. Hence we have $n-3$ $a_j$'s equal to 1, one $a_l$ greater than $1$ and one negative $a_k\le -(n-1)$. We can check that $\partial^2 f/\partial a_l = h''(a_l), \partial^2 f/\partial a_k = h''(a_k) > 0$ so this case is ruled out as well. Our only case is when there are $n-2$ $a_j$'s equal to 1 and one $a_k=-(n-1)$
10.05.2024 04:04
First Solution: By taking $a_1=a_2=\cdots=a_{n-1}=b=1$ and $a_n = -(n-1)$, we have $\lambda \geq \frac{n-1+\sqrt{n-1}}{\sqrt n} = c$. So we prove that $c$ is minimal. First, I claim that for $\lambda$ minimal, $a_1+a_2+\cdots+a_n = 0$. Suppose otherwise, and let $a_1+a_2+\cdots+a_n=np$ with $\lambda$ minimal. Subtracting $p$ from each of $a_1, a_2, \dots, a_n, b$, the term $\sqrt{n\left|\sum_{i=1}^n a_i\right|}$ decreases by $n\sqrt p$, while the term $\sum_{i=1}^n \sqrt{|a_i|}$ decreases by at most $n\sqrt p$ by convexity of the function $\sqrt x$. So the minimum value of $\lambda$ with respect to these constraints decreases, contradiction. Now, given $a_1+a_2+\cdots+a_n = 0$, we will show the inequality for $\lambda=c$. Let $b_1, b_2, \cdots, b_s \geq 0$ and $c_1, c_2, \cdots, c_t < 0$ with $\bigcup a_i = \bigcup b_i \sqcup \bigcup c_i$, and let $b_1+b_2+\cdots+b_s = A = -(c_1+c_2+\cdots+c_t)$. Now, WLOG $b \geq 0$. Then \begin{align*} \sum_{i=1}^n \sqrt{|a_i|} &= (\sqrt{b_1}+\sqrt{b_2}+\cdots+\sqrt{b_s})+(\sqrt{c_1}+\cdots+\sqrt{c_t}) \\ &\geq \sqrt A(\sqrt s + \sqrt t) \end{align*}by Cauchy-Schwarz. But $\sqrt{|x|}$ is convex on $\mathbb R \setminus \{0\}$, so by Karamata, \begin{align*} \sqrt{|b_1-b|} + \sqrt{|b_2-b|} + \cdots + \sqrt{|b_s-b|} &\geq \sqrt{A-sb} \\ \sqrt{|c_1-b|} + \sqrt{|c_2-b|} + \cdots + \sqrt{|c_t - b|} &\geq (t-1)\sqrt b + \sqrt{A+b}. \end{align*}So the left-hand side is at least \begin{align*} L &= c\left(\sqrt{A-sb} - (t-1)\sqrt b + \sqrt{A+b}\right) \\ &\geq c \operatorname{min} \left\{2\sqrt A, (s-1)\sqrt{\frac At} + \sqrt{A\left(1+\frac 1t\right)}\right\} \end{align*}as the function is concave in $b$. It remains to show that \begin{align*} 2c \sqrt A &\geq \sqrt A(\sqrt s + \sqrt t) \\ c\left((s-1)\sqrt{\frac 1t}+\sqrt{1+\frac 1t}\right) &\geq \sqrt s + \sqrt t. \end{align*}The first inequality is obvious as $\sqrt s + \sqrt t \leq \sqrt{2n} \leq 2c$. The second inequality is equivalent to \[\frac{s-1+\sqrt{t+1} - \sqrt n}{\sqrt n} \geq \frac{\sqrt{st}+t-(n-1+\sqrt{n-1})}{n-1+\sqrt{n-1}}.\]Now observe that \begin{align*} s-1+\sqrt{t+1} - \sqrt n &\geq s-1-\sqrt{s-1} \\ \sqrt{st} + t - (n-1)-\sqrt{n-1} &\leq \sqrt{n-1}(\sqrt s - 1). \end{align*}So it remains to show that \[\frac{s-1-\sqrt{s-1}}{\sqrt n} \geq \frac{\sqrt{n-1}(\sqrt s - 1)}{n-1+\sqrt{n-1}}\]holds, which is easy to check. Equality occurs when $t = 1$ and $s = n-1$, as expected from the equality case. Second Solution: Here, we prove the upper bound alternatively. We have \begin{align*} A_1 &= \sqrt{(n-1)|a_1-b|} + \sqrt{|b-a_2|} + \cdots + \sqrt{|b-a_n|} + \sqrt{|a_1+a_2+\cdots+a_n|} \\ &\geq \sqrt{(n-1)|a_1-b| + |b-a_2| + \cdots+|b-a_n| + |a_1+a_2+\cdots+a_n|} \\ &\geq \sqrt{|na_1|} \end{align*}by convexity and the triangle inequality. But now, summing $A_1, A_2, \dots, A_n$, we have \[A_1+A_2+\cdots+A_n = \left(n-1+\sqrt{n-1}\right)\sum_{i=1}^n \sqrt{|a_i-b|} + n\sqrt{\sum_{i=1}^n |a_i|} \geq \sqrt n \sum_{i=1}^n\sqrt{|a_i|}\]which precisely gives the inequality.