Problem. Determine the minimum for the expression \[E(x_1,x_2,\ldots,x_n) = (n-1)\sum_{k=1}^n x_k^2 + n\prod_{k=1}^n x_k\] where $x_k$, $1\leq k \leq n$, are non-negative real numbers having $\displaystyle \sum_{k=1}^n x_k = n$. Danube Cup 2010 Solution. The case $n=1$ is trivial, since then $E \equiv 1$. The case $n=2$ is also trivial, since then $E \equiv 4$. Suppose in the sequel $n\geq 3$. Let $\displaystyle D = \Big \{ x = (x_1,x_2,\ldots,x_n) \mid x_k \geq 0, \ 1\leq k \leq n, \ \sum_{k=1}^n x_k = n \Big \} \subset \mathbb{R}^n$. Then $E : D \to \mathbb{R}$ is a polynomial function, hence of class $C^{\infty}$; since $D$ is a bounded and closed domain (therefore compact), Weierstrass' Theorem states that $E$ reaches its extrema on $D$, thus $\displaystyle \min_{x \in D} E(x)$ exists (and is finite). Build the Lagrange function \[\displaystyle L(x_1,x_2,\ldots,x_n) = E(x_1,x_2,\ldots,x_n) - \lambda\Big (\sum_{k=1}^n x_k - n \Big ),\] where $\lambda$ is a real-number parameter. The method of Lagrange multipliers finds the critical points (minimum, maximum and saddle) in the interior of domain $D$ (with strict inequalities $x_k > 0$), as solutions of the system of the partial derivatives of $L$, equaled to zero. It remains, by other means, to determine such points on the border $\partial D$ of the domain (with equalities $x_k=0$). But if at least one $x_k=0$, then $\displaystyle E = (n-1)\sum_{j\neq k} x_j^2 \geq \Big(\sum_{j\neq k}x_k\Big)^2 = n^2$, by Cauchy-Schwarz inequality (with equality for $x_j = \dfrac {n} {n-1}$, $j\neq k$), therefore $\displaystyle \min_{x \in \partial D} E(x) = n^2$ (the maximum on the border is reached when all variables are null, except one equal to $n$, so $\displaystyle \max_{x \in \partial D} E(x) = (n-1)n^2$). Consider now the system of the partial derivatives of $L$ (with respect to the variables $x_k$), equaled to zero. The partial derivative $\dfrac {\partial L} {\partial \lambda}$ (with respect to $\lambda$), equaled to zero, gives us precisely the restriction $\displaystyle \sum_{k=1}^n x_k - n = 0$ (and thus usually plays no other role). Let us also denote $\displaystyle P = \prod_{k=1}^n x_k$. Let then have the system of equations $\dfrac {\partial L} {\partial x_k} = 2(n-1)x_k + nP\dfrac {1} {x_k} - \lambda = 0, \ 1\leq k \leq n.$ By subtracting the equations for indices $1\leq i\neq j \leq n$ we get \[(x_i-x_j)(2(n-1)x_ix_j - nP) = 0.\] Therefore either $x_i=x_j$, or $x_ix_j = \dfrac {n} {2(n-1)} P$. Denote by $y_k$, $1\leq k\leq s\leq n$, the distinct values in the multiset of the variables $x_1,x_2,\ldots,x_n$, and by $n_k$ their multiplicities, hence $\displaystyle \sum_{k=1}^s n_s = n$ and $\displaystyle \sum_{k=1}^s n_sy_s = n$. Now comes the key observation - if $s \geq 3$, then it must be $y_ky_i = \dfrac {n} {2(n-1)} P = y_ky_j$ for three distinct indices $1 \leq i,j,k \leq s$, hence $y_i=y_j$, absurd. It follows that $s=1$ or $s=2$. The case $s=1$ implies all variables equal, thus of value $1$ each, and then $E(1,1,\ldots,1) = (n-1)n + n = n^2$, the same minimum value as that already found on the border. The case $s=2$ implies $a$ variables equal to $u$, and $b$ variables equal to $v$, with $a, b \geq 1$, $a+b=n$, $au+bv=n$, but also $uv = \dfrac {n} {2(n-1)} P$. Then $E(u, \ldots, v,\ldots) = (n-1)(au^2 + bv^2) + nP =$ $ (n-1)(au^2 + bv^2 + 2uv) =$ $ (n-1)(n(u+v) - (n-2)uv)$ (our system of equations reduces to just $2(n-1)(u + v) - \lambda = 0$). We will show that $E(u, \ldots, v,\ldots) \geq n^2$, which solves the problem. Let us make the substitution $v = \dfrac {n-au} {b}$ in order to get $E = \dfrac {n-1} {b} \left (n(n+(b-a)u) - n(n-2)u + (n-2)au^2 \right ) $ $ = \dfrac {n-1} {b} \left ((n-2)au^2 - n(n-2 +a-b)u + n^2 \right ) $ $= \dfrac {n-1} {b} \left ((n-2)au^2 - 2n(a-1)u + n^2 \right ).$ The minimum of the quadratic in the brackets is reached for $u_0 = \dfrac {n(a-1)} {(n-2)a}$ $E \geq \dfrac {n-1} {b} \left ((n-2)a\dfrac {n^2(a-1)^2} {(n-2)^2a^2} - 2n(a-1)\dfrac {n(a-1)} {(n-2)a} + n^2\right) =$ $ \dfrac {n-1} {b} n^2 \left (1 - \dfrac {(a-1)^2} {(n-2)a} \right ).$ To show that $E \geq n^2$ is therefore enough to have $(n-1)(n-2)a - (n-1)(a-1)^2 \geq (n-2)ab, \textrm{or} $ $ (n-2)a(n-1-b) = (n-2)a(a-1) \geq (n-1)(a-1)^2, \textrm{or} $ $(a-1)\left ((n-2)a - (n-1)(a-1) \right ), \& \textrm{i.e.} $ $(a-1)((n-1) - a) \geq 0, $ which is clearly true. Although it may look equality is now reached also for $a=1$ or $a=n-1$, the value $a=1$ leads to $u_0 = 0$, while the value $a=n-1$ leads to $b=1$ and $v_0 = n-(n-1)u_0 = 0$, values which are excluded from the interior of the domain (but have been found on its border). Since these extremal values cannot verify $uv = \dfrac {n} {2(n-1)} P$, it follows those are otherwise critical points, not a global minimum. Remark. An alternative, more elegant, to finish the proof is to start from $a, b \geq 1$, $a+b=n$, $au+bv=n$ (and $uv = \dfrac {n} {2(n-1)} P$), so $E(u, \ldots, v,\ldots) = (n-1)(au^2 + bv^2 + 2uv)$. We have $2uv = (u+v)^2 - (u^2 + v^2)$ and $(a-1)u^2 + (b-1)v^2 > \dfrac {((a-1)u + (b-1)v)^2} {(a-1) + (b-1)} = \dfrac {(n - (u+v))^2} {n-2}$, from Cauchy-Schwarz. The inequality is este strict, since equality cases ($a=1$, or $b=1$, or $u=v$) lead to a contradiction, as above. Then $E > (n-1)\left (\dfrac {(n - (u+v))^2} {n-2} + (u+v)^2\right ) $ $ = \dfrac {n-1} {n-2} \left ((n-1)(u+v)^2 - 2n(u+v) + n^2\right) $ $= \dfrac {n-1} {n-2} \left (\dfrac {((n-1)(u+v) - n)^2} {n-1} + \dfrac {n-2} {n-1} n^2 \right) $ $= n^2 + \dfrac {1} {n-2} ((n-1)(u+v) - n)^2 $ $ \geq \& n^2.$ Another essential remark is that, even if the statement were given as $x_k >0$, $1\leq k \leq n$, after the use of the Lagrange multipliers method, we still ought to have studied the cases when some of the values $x_k$ were zero,since maybe the global minimum was obtained at $x_k \to 0$ for some values of $k$ (the border of the domain is the same now and then).

this seems a very hard solution, i'm wondering if the only one in the competion who solved it used this solution coudn't there be a simpler solution still based on strum method? where did you learn the weierstrass compact.... method , i am in the 9th grade and didn't manage to understand it frow wikipedia, and if it's not to much you don't happen to have a pdf with the solutions to the entire contest?? problem 4 is the only one besides this one i haven't manage to solve...

Is my proof wrong? I think can do that: Case $x_{i}>0$ with all i. Let $f(x_{1},x_{2},...,x_{n})=(n-1)\sum_{i=1}^{n} (x_{i})+nx_{1}x_{2}..x_{n}$ easy to see $f(x_{1},x_{2},...,x_{n}) \geq f(\sqrt{x_{1}x_{2}},\sqrt{x_{1}x_{2}},x_{3},...,x_{n})$ Because $x_{i}$ is similar then with Stronger Mixing Variables we have $f(x_{i})$ min when $x_{i}=x_{j}$ with all i,j. then min is: $(n-1)n+n=n^{2}$ Case if have k number $x_{i}$ is not equal 0. use Cauchy have $f(x_{j})\geq (n-1)(\frac{n^{2}}{k})$ then f min when $k=n-1$ All case for me $f_{min}=n^{2}$ when all $x_{i}=1$ or have only $x_{j}=0$

it's a great solution!!, thankyou at first i have tried unsuccesfuly E(X1,,,,,,XN)>E(X1+R,X2-R,......XN) and E(X1,,,,XN)>E(1,X1+X2-1,,,,,,XN) it seems the idea was to leave the product constant

I thought that, let $E(x_1,x_2,\ldots,x_n) = (n-1)(x_1^2+x_2^2+\cdots +x_n^2) + nx_1x_2\cdots x_n \geq (n-1)^2+(n-1)x_n^2+nx_1x_2\cdots x_n \geq (n-1)^2$. So $x_1=x_2=\cdots =x_{n-1} = \dfrac {n}{n-1}$, plus $x_n=0$.

First, your inequality only holds for $x_n\leq 1$. Ok, we can accept that, since from $\sum_{k=1}^n x_k = n$ it follows there must exist an $x_m \leq 1$, and wlog we may take $m=n$. But your conclusion means what? That the minimum is $(n-1)^2$? That is false, since it has been proved the minimum is $n^2$; moreover, for your values we get precisely the value $n^2$. You probably derived those values from the Cauchy-Schwarz, but the whole thing is quite wrong, and proves nothing.

paul1703 wrote: Let $n\ge3$ be a positive integer. Find the real numbers $x_1\ge0,\ldots,x_n\ge 0$, with $x_1+x_2+\ldots +x_n=n$, for which the expression \[(n-1)(x_1^2+x_2^2+\ldots+x_n^2)+nx_1x_2\ldots x_n\] takes a minimal value. Beautiful problem !

Attachments:

maybe we can use suranyi inequality

vntbqpqh234 wrote: Is my proof wrong? I think can do that: Case $x_{i}>0$ with all i. Let $f(x_{1},x_{2},...,x_{n})=(n-1)\sum_{i=1}^{n} (x_{i})+nx_{1}x_{2}..x_{n}$ easy to see $f(x_{1},x_{2},...,x_{n}) \geq f(\sqrt{x_{1}x_{2}},\sqrt{x_{1}x_{2}},x_{3},...,x_{n})$ Because $x_{i}$ is similar then with Stronger Mixing Variables we have $f(x_{i})$ min when $x_{i}=x_{j}$ with all i,j. then min is: $(n-1)n+n=n^{2}$ Case if have k number $x_{i}$ is not equal 0. use Cauchy have $f(x_{j})\geq (n-1)(\frac{n^{2}}{k})$ then f min when $k=n-1$ All case for me $f_{min}=n^{2}$ when all $x_{i}=1$ or have only $x_{j}=0$ The condition $x_{1}+x_{2},...,x_{n})=n$ doesn't hold for $\sqrt{x_{1}x_{2}},\sqrt{x_{1}x_{2}},x_{3},...,x_{n}$

Let $f(x_1,x_2, \dots,x_n) = (n-1)\sum\limits_{i=1}^n x_i^2 + n\prod\limits_{i=1}^n x_i$. I claim $f(x_1,x_2, \dots, x_n) \geq n^2$ for every such sequence. Then lets suppose there exists a pair $(i,j)$ such that: $2(n-1)x_ix_j \leq n\prod\limits_{i=1}^n x_i$. Lets suppose without loss of generality that pair is (1,2). I claim $f(x_1,x_2, \dots, x_n) \geq f(0,x_1 + x_2, x_3, \dots, x_n)$. Let $S = \sum\limits _{i=3}^n x_i^2, P = n \prod\limits_{i=3}^n x_i$ $\Leftrightarrow (n-1)[(x_1 + x_2)^2 + S] \leq (n-1)(x_1^2 + x_2^2 + S) + Px_1x_2$ $\Leftrightarrow (n-1)[2x_1x_2] \leq Px_1x_2 \Leftrightarrow 2(n-1)x_1x_2 \leq n \prod\limits_{i=1}^n x_i$. So we've proved that $x_1 = 0$ is optimal in this case, but then $f(0,x_2, \dots, x_n) = (n-1)(\sum\limits_{i=2}^n x_i^2) \geq n^2$ by Cauchy inequality. Now it suffices to prove the case in which for every pair $(i,j), 2(n-1)x_ix_j > n\prod\limits_{i=1}^n x_i $ (In particular $x_i \neq 0$) I claim $f(x_1,x_2, \dots, x_n) \geq f(\frac{x_1+x_2}{2}, \frac{x_1+x_2}{2}, x_3, \dots, x_n)$ (we are using $(1,2)$, but it works for every $(i,j).$) To prove it, I will use the same $S,P$ used in the previous case. The desired inequality is if and only if $$(n-1)(x_1^2 + x_2^2 + S) + Px_1x_2 > (n-1)( \frac{(x_1 + x_2)^2}{2} + S) + \frac{(x_1 + x_2)^2}{4} P $$$$\Leftrightarrow (n-1)\frac{(x_1 -x_2)^2}{2} > P \frac{(x_1 - x_2)^2}{4} $$$$\Leftrightarrow 2(n-1)x_1x_2 > n \prod\limits_{i=1}^n x_i $$ Thus, by Stronger Mixing Variables, $f$ is minimal when $ x_i = 1$ for every $i$, thus $f(1,1,\dots,1) = n^2$ is the minimal value.

1) Actually, this is AC-Theorem (AC-Arithmetic Compensation): If $f(x_1,x_2,\ldots,x_n)$ is a symmetric continuous function such that $$f(x_1,x_2,x_3,\ldots,x_n)\ge f(0,x_1+x_2,x_3,\ldots,x_n)$$for all $x_1,x_2,\ldots,x_n$ satisfying $$f(x_1,x_2,x_3,\ldots,x_n)<f(\frac{x_1+x_2}{2},\frac{x_1+x_2}{2},x_3,\ldots,x_n),$$then $f(x_1,x_2,\ldots,x_n)$ is minimum when $x_1=x_2=\dots=x_n$ or $x_1=0$. 2) We have a simple solution by using EV-Theorem: If $x_1+x_2+\dots+x_n=constant$ and $x_1^2+x_2^2+\dots+x_n^2=constant$, then the product $x_1x_2\dots x_n$ is minimum when either $x_1=0$ or $0<x_1\le x_2=x_3=\cdots=x_n$. 3) Another simple solution is by using AM-Corollary (AM-Arithmetic Mean): If $f(x_1,x_2,\ldots,x_n)$ is a symmetric continuous function satisfying $$f(x_1,x_2,\ldots,x_{n-2},x_{n-1},x_n)\ge f(\frac{x_1+x_{n-1}}{2},x_2,\ldots,x_{n-2},\frac{x_1+x_{n-1}}{2},x_n)$$for $x_1\ge x_2\ge\dots\ge x_n$, then $$f(x_1,x_2,\ldots,x_{n-1},x_n)\ge f(t,t,\ldots,t,x_n),\ \ \ \ t=\frac{x_1+x_2+\dots+x_{n-1}}{n-1}.$$