Find the minumum of the value $k$ such two condition $x_1+x_2+ \cdots +x_k<\frac{x_1^3+x_2^3+ \cdots +x_k^3}{2}$

Question

Let $x_1,x_2,\ldots, x_k$ be positive real numbers satisfying \begin{cases} x_1+x_2+ \cdots +x_k<\frac{x_1^3+x_2^3+ \cdots +x_k^3}{2};\\ x_1^2+x_2^2+ \cdots +x_k^2<\frac{x_1+x_2+ \cdots +x_k}{2}.\end{cases} Find minimal value of $k$ satisfying those equations.

It is said this problem creat Kvant? And the answer is $k_{\min}=516$. See here :hard inequality.

ADD it Michael Rozenberg take this problem from the 28-th Tournament of Towns, autumn 2006, problem 7 and he say maybe it is open problem in Canada.

when $k=516$,I found this example such condition $$x_{1}=5.169,x_{2}=x_{3}=\cdots=x_{516}=\dfrac{1}{8}$$ because $$x^2_{1}+x^2_{2}+\cdots+x^2_{516}=5.169^2+\dfrac{515}{64}=34.765436,$$$$~~\dfrac{1}{2}(x_{1}+x_{2}+\cdots+x_{516})=\dfrac{1}{2}(5.169+\dfrac{515}{8})=34.772$$ and

$$(x_{1}+x_{2}+\cdots+x_{516})=(5.169+\dfrac{515}{8})=69.544$$ $$\dfrac{1}{2}(x^3_{1}+x^3_{2}+\cdots+x^3_{516})=\dfrac{1}{2}(5.169^3+\dfrac{515}{512})=69.557050592$$

Answer 1

We reorder the set to $x_1\ge x_2\ge\dots\ge x_k$. If all $0\lt x_j\lt\sqrt{2}$ then the inequality

$$\tag{1}x_1+\dots+x_k\lt\dfrac{x_1^3+\dots+x_k^3}{2}$$

does not hold. Therefore $x_1\ge\sqrt{2}$. If all $x_j\gt\dfrac{1}{2}$ then the inequality

$$\tag{2}x_1^2+\dots+x_k^2\lt\dfrac{x_1+\dots+x_k}{2}$$

does not hold. Therefore $0\lt x_k\le\dfrac{1}{2}$ and we get $k\gt1$. For $x_j\gt0$ we have $\dfrac{x_j}{2}-x_j^2\le\dfrac{1}{16}$, the value increases for $x_j\le\dfrac{1}{4}$ with growing $x_j$, the value decreases for $x_j\ge\dfrac{1}{4}$ with growing $x_j$ and the inequality $(2)$ does not hold if $x_1\gt 2k$. Therefore the parameters $(x_j)_j$ are bounded.

For any solution $\hat x_1,\dots,\hat x_k$ we have $\hat x_1\ge\sqrt{2}$ and therefore we can increase $\hat x_1$ and the inequality $(1)$ still holds. But in increasing $\hat x_1$ we will finally get an equality in the inequality $(2)$ and therefore there exists a set $(\hat x_j)_j$ such that

$$\tag{3}\hat x_1^2+\dots+\hat x_k^2=\dfrac{\hat x_1+\dots+\hat x_k}{2}$$

is true. Hence we will find the maximum

$$\tag{4}f((x_j)_j):=f(x_1,\dots,x_k)=\sum_{j=1}^k\left\{\dfrac{x_j^3}{2}-x_j\right\}$$

under the condition $(3)$

$$\tag{5}g((x_j)_j):=g(x_1,\dots,x_k)=\sum_{j=1}^k\left\{\dfrac{x_j}{2}-x_j^2\right\}=0.$$

Because the $x_j$ are bounded and the set defined by $(5)$ is closed, the maximum of the function $f((x_j)_j)$ exists. With the Lagrange multiplier $\lambda$ we define

$$\tag{6}F((x_j)_j,\lambda):=f((x_j)_j)+\lambda g((x_j)_j).$$

The maximum can only exists at points where the equalities

$$\tag{7}\dfrac{\partial F((x_j)_j,\lambda)}{\partial x_j}=\dfrac{3}{2}x_j^2-1+\lambda\left(\dfrac{1}{2}-2x_j\right)=0$$ $$\tag{8}\dfrac{\partial F((x_j)_j,\lambda)}{\partial\lambda}=g((x_j)_j)=0$$

hold. With $x_1\ge\sqrt{2}$ we determine the multiplier $\lambda$ to

$$\tag{9}\lambda=\dfrac{3x_1^2-2}{4x_1-1}.$$

But then the polynomials of degree $2$ for the other parameters $x_j$ in $(7)$ give either $x_1$ or a second value. We already know that there are at least two values, one less than $\dfrac{1}{2}$ and one more than $\sqrt{2}$. Therefore we rewrite the conditions $(4)$ and $(5)$ to

$$\tag{10}f(x_1,x_2):=k_1\left\{\dfrac{x_1^3}{2}-x_1\right\}+k_2\left\{\dfrac{x_2^3}{2}-x_2\right\}$$ $$\tag{11}g(x_1,x_2):=k_1\left\{\dfrac{x_1}{2}-x_1^2\right\}+k_2\left\{\dfrac{x_2}{2}-x_2^2\right\}=0$$

with $1\le k_1\lt k$ and $k_1+k_2=k$ and we will search the maximum for the functions $f(x_1,x_2)$ under the condition $g(x_1,x_2)=0$. The equation $(11)$ gives

$$\tag{12}x_2=h(x_1):=\dfrac{1}{4}\pm\sqrt{\dfrac{1}{16}-\dfrac{k_1}{k_2}\left\{x_1^2-\dfrac{x_1}{2}\right\}}.$$

But the equation $(12)$ only gives a solution for

$$\tag{13}\dfrac{1}{4}\left\{1-\sqrt{1+\dfrac{k_2}{k_1}}\right\}\le x_1\le\dfrac{1}{4}\left\{1+\sqrt{1+\dfrac{k_2}{k_1}}\right\}=:\alpha$$

when the root in $(12)$ is not negative. If $\alpha\ge\sqrt{2}$ we have to find the maximum in the intervall $x_1\in[\sqrt{2},\alpha]$.

The function $\dfrac{x^3}{2}-x$ decreases for $0\le x\le\sqrt{{2 \over 3}}$ with growing $x$ and it increases for $x\ge\sqrt{{2 \over 3}}$ with growing $x$. If we take the positive sign in $(12)$ the function $f(x_1,x_2)$ has a value less than $f(\alpha,1/4)$ because $\alpha\ge\sqrt{2}$ and the condition $0\lt x_2\lt\dfrac{1}{2}$ for a solution. The value was always less than $0$.

For the negative sign in $(12)$ we have to find the maximum in the interval $x_1\in[\sqrt{2},\alpha]$. We do this by iteration. We start with $\xi_n=\sqrt{2}$ with $n=0$:

1. First we determine $\delta_n=\dfrac{\xi_n+\alpha}{2}$.
2. If the value $f(\xi_n, h(\xi_n))$ is more than $0$ we have found the smallest value $k$.
3. Otherwise we check whether $f(\xi_n+\delta_n, h(\xi_n))$ is less than $0$. Then the value $f(\xi_n+\delta_n, h(\xi_n+\delta_n))$ must also be less than $0$ because $x_2=h(\xi_n+\delta_n)\ge h(\xi_n)$ with $\delta_n\gt 0$ (see $(12)$) and the function $f(x_1,x_2)$ decreases for $x_2\le\sqrt{\dfrac{2}{3}}$ with growing $x_2$. Then we restart the process with $\xi_{n+1}=\xi_n+\delta_n$ at $1$.
4. Otherwise we check whether the value $f(\xi_n+\delta_n, h(\xi_n+\delta_n))$ is more than $0$. Then we have found the smallest k.
5. If all tests failed we restart at $3$ with half the value $\delta_{n}$.

The iteration either fails for a combination $k$, $k_1$ or we have found the smallest value $k$. The case that the function $f$ has a maximum of $0$ did not occur. In that case the iteration would not work.

Starting with $k=2$ and running through the values $1\le k1\lt k$ the process terminates with $k=516$, $k_1=1$, $x_1=5.13931983067114$, $x_2=0.122708944529751$.

Answer 2

Conditional extremum

Let us maximize the function $$f(\vec x) = \sum\limits_{i=1}^k(x_i^3-2x_i)$$ on the condition $$c(\vec x) = \sum\limits_{i=1}^k (x_i-2x_i^2) = 0$$ for the given $k$ and positive $x_1, x_2\dots x_k.$

Note that solutions on the edges of the area reduces $k$ and therefore are unacceptable.

Also, the solution in the form $$x_j = t,\quad j=1\dots k,$$ gives $$t-2t^2=0\rightarrow\ t={1\over2}\rightarrow f(\vec x) = - {7\over8}k < 0$$ and isn't valid.

A conditional maximum within a region can be found by the method of Lagrange multipliers and corresponds to one of the stationary points of the function

$$f(\vec x,\lambda) = \sum\limits_{i=1}^k(x_i^3-2x_i)+\lambda\sum\limits_{i=1}^k (x_i-2x_i^2).$$ That gives the system $$f'_\lambda =0,\quad f'_{x_j}=0,\quad j=1\dots k,$$ or $$\sum\limits_{i=1}^k (x_i-2x_i^2)=0,\quad 3x_j^2-2 + \lambda(1-4x_j) = 0,\quad j=1\dots k,$$ $$3x_j^2-4\lambda x_j + \lambda -2 = 0,\quad j=1\dots k.$$

Values Relationship

Let $x_j \in \{u, v\},\ 0<u<v,$ then $$u+v = {4\over3}\lambda,\quad uv = {\lambda-2\over3},$$ $$u+v = {4\over3}(3uv+2),\quad\rightarrow 12uv-3v = 3u-8,$$ $$v = {3u-8\over3(4u-1)},\quad u\in\left(0,{1\over4}\right),\quad v\in\left({8\over3}, \infty\right),$$ and substitution $t= 1-4u$ gives $$u={1-t\over4},\quad v = {29\over12t}+{1\over4},\quad t\in(0,1)$$ Let WLOG $$x_j = \begin{cases} \dfrac{1-t}{4},\quad j=1\dots b\\[4pt] \dfrac{29}{12t}+\dfrac14,\quad j=b+1\dots k. \end{cases}\tag1$$

Solution for real parameters

Using $(1),$ one can calculate $$8\sum\limits_{i=1}^k (x_i-2x_i^2) = b\left(2(1-t) - (1-t)^2\right) + (k-b)\left(2\left({29\over3t} + 1\right) - \left({29\over3t} + 1\right)^2\right) = -(k-b){841\over9t^2} + k-bt^2 = k(1-t^2) + (k-b)\left(t^2-{841\over9t^2}\right)> 0$$ (see also Wolfram Alfa), $$64\sum\limits_{i=1}^k (x_i^3-2x_i) = b((1-t)^3 - 32(1-t)) + (k-b)\left(\left({29\over3t}+1\right)^3 - 32\left({29\over3t}+1\right)\right)$$ $$ = k((1-t)^3 - 32(1-t)) + (k-b)\left(\left({29\over3t}+1\right)^3 - (1-t)^3 - 32\left({29\over3t}+1\right)+32(1-t)\right)$$ $$ = k(1-t)(-31-2t+t^2) + (k-b)\left({29\over3t}+t\right) \left(\left({29\over3t}+1\right)^2 + \left({29\over3t}+1\right)(1-t) + (1-t)^2 - 32\right) > 0,$$ and that leads to the system of $t$ and $b$ in the form of $$\begin{cases} 9kt^2(1-t^2) - (k-b)(841-9t^4) > 0\\ 27kt^3(1-t)(-31-2t+t^2) + (k-b)(29+3t^2)(841 + 261t - 348t^2 - 27t^3 + 9t^4) > 0\\ t\in(0,1),\quad b\in[1,k-1] \end{cases}\tag2$$ (see also Wolfram Alfa).

Summation of $(2.1)$ factor $\ 3t(31+2t-t^2)>0\ $ and $(2.2)$ factor $\ 1+t>0\ $ leads to the inequality for $t:$ $$(841-9t^4)3t(31+2t-t^2) - (t+1)(29+3t^2)(841+261t-348t^2-27t^3+9t^4) < 0,$$ or $$(3t+29)(3t^2+29)(3t^2+58t-29)<0$$ (see also Wolfram Alfa),

with the solution $$t\in(0, t_m],\quad t_m = {1\over3}(4\sqrt{58} - 29)\approx0.487697,$$ wherein $t_m$ corresponds to the equal sign of the inequalities in $(2.1)-(2.2).$

The system $(2)$ on the condition $t=t_m$ can be presented in the form of $$\begin{cases} 1.63149k - 840.491(k-b) > 0\\ -50.923k + 26233.9(k-b) > 0\\ b\in[1,k-1], \end{cases}$$ $$k \approx 515,2 (k-b).$$ Solution for real $k$ and $b$ shows that the least integer allowable values are $$\mathbf{k=516,\quad b=515}.$$

One solution for known parameters

Earlier it was proved that solutions for $k<516$ are impossible. To find one solution in the case of known integer values $k = 516$ and $b = 515,$ one can use the relations $(1)$ in the form of $$x_j = \begin{cases} \dfrac{1-t_m}{4},\quad j=1\dots 515\\[4pt] \dfrac{29}{12t_m}+\dfrac14,\quad j=516\dots k, \end{cases}$$ or $$x_j = \begin{cases} \dfrac{8-\sqrt{58}}{3}\approx0.12807563,\quad j=1\dots 515\\[4pt] \dfrac{8+\sqrt{58}}{3}\approx5.20525770,\quad j=516, \end{cases}$$ but this set doesn't satisfy the first inequality. Substitution of $$u_m = \dfrac{8-\sqrt{58}}{3},$$ to the first inequality $$515(u_m^3-2u_m) + v^3-2v > 0$$ gives $v>5.20792$, and the values $u=u_m,\ v= 5.208\ $ give the solution.

The set of solutions for known parameters

In order to find the full range of possible solutions in the case of known integer values $k = 516$ and $b = 515,$ one should abandon the relations $(1)$ and look for a solution in the form of $$x_j = \begin{cases} u,\quad j=1\dots b\\[4pt] v,\quad j=b+1\dots k. \end{cases}$$

Then the allowable area of $t$ can be obtained from the system $$\begin{cases} f(\vec x) = 515(u^3-2u) + v^3-2v > 0\\ c(\vec x) = 515(u-2u^2) + v-2v^2 >0 > 0. \end{cases}$$

The bounds of the area can be found from the system of according equations: $$\left[\begin{align} &\begin{cases} 515(u^3-2u) + v^3-2v > 0\\ 515(u-2u^2) + v-2v^2 = 0 \end{cases}\\ &\begin{cases} 515(u^3-2u) + v^3-2v = 0\\ 515(u-2u^2) + v-2v^2 > 0 \end{cases} \end{align}\right.$$

The analysis of solutions for the first and the second cases shows that $$\begin{cases} u\in(0.121883, 0.1344),\\ v\in\left(\dfrac{\sqrt[3]{-13905 u^3 + \sqrt{(27810 u - 13905 u^3)^2 - 864} + 27810 u}}{3 \sqrt[3]2}\\ + \dfrac{2\sqrt[3]2}{\sqrt[3]{-13905 u^3 + \sqrt{(27810 u - 13905 u^3)^2 - 864} + 27810 u}},\\ \dfrac{\sqrt{-8240u^2 + 4120u + 1} + 1}{4}\right) \end{cases}$$

That gives:

for $u=0.125\quad 5.16867<v<5.16967$ (see also Wolfram Alfa),

for $u=0.122709\quad 5.13899<v<5.13932$ (see also Wolfram Alfa), etc.

Conclusion

The analysis shows that $$\boxed{k=516}$$ is the required minimum of value $k.$

Done!

Answer 3

I restate the problem as follows:

Find the smallest positive integer $k$ such that there exist positive real numbers $x_1, x_2, \cdots, x_k$ satisfying $2(x_1^2+x_2^2 + \cdots + x_k^2) < x_1 + x_2 + \cdots + x_k < \frac{1}{2}(x_1^3 + x_2^3 + \cdots + x_k^3).$

My solution:

Clearly, when $k=1, 2$, impossible. In the following, assume that $k \ge 3.$

Let $y_i = \frac{x_1 + x_2 + \cdots + x_k}{2(x_1^2+x_2^2 + \cdots + x_k^2)}x_i,\ \forall i$. We have $y_i > 0,\ \forall i$ and $2(y_1^2+y_2^2 + \cdots + y_k^2) = y_1 + y_2 + \cdots + y_k < \frac{1}{2}(y_1^3 + y_2^3 + \cdots + y_k^3)$.

According to Vasc's Equal Variable Theorem [1, Corollary 1.9], there exist $0 < z_1 = z_2 = \cdots = z_{k-1} \le z_k$ such that $$y_1 + y_2 + \cdots + y_k = z_1 + z_2 + \cdots + z_k,$$ $$y_1^2 + y_2^2 + \cdots + y_k^2 = z_1^2 + z_2^2 + \cdots + z_k^2,$$ $$\mathrm{and}\quad y_1^3 + y_2^3 + \cdots + y_k^3 \le z_1^3 + z_2^3 + \cdots + z_k^3.$$ Remark: Without using Equal Variable Theorem, actually it is not hard to prove this result.

Thus, it holds that $2(z_1^2+z_2^2 + \cdots + z_k^2) = z_1 + z_2 + \cdots + z_k < \frac{1}{2}(z_1^3 + z_2^3 + \cdots + z_k^3)$.
By denoting $z_1 = z_2 = \cdots = z_{k-1}=b, \ z_k = a$, we have $$0 < b \le a, \quad 2((k-1)b^2 + a^2) = (k-1)b + a < \frac{1}{2}((k-1)b^3 + a^3)$$ $$\Longleftrightarrow$$ $$b \in (0, \frac{1}{2}),\quad a = \frac{1}{4} + \frac{1}{4}\sqrt{Q}, \quad (2b(1-2b)(k-1)-7)\sqrt{Q} > 2b(-8b^2+6b+13)(k-1) + 7$$ $$\Longleftrightarrow$$ $$b \in (0, \frac{1}{2}),\quad a = \frac{1}{4} + \frac{1}{4}\sqrt{Q}, \quad k > \frac{2(-4b^2+2b+7)(b^2-b+2)}{b(1-2b)^3}.\qquad\qquad (3)$$ where $Q = 8b(1-2b)k + (4b-1)^2$.

Let $f(b) = \frac{2(-4b^2+2b+7)(b^2-b+2)}{b(1-2b)^3}$. It is easy to prove that $515 < \min_{b\in (0, \frac{1}{2})} f(b) < 516$. Thus, there exist $b\in (0, \frac{1}{2})$ and $b\le a$ satisfying (3) if and only if $k \ge 516.$ Thus, we have $k_{\min} = 516.$

Remark: When $k \ge 516$, (3) is always true by letting $b = \frac{1}{8}, \ a = \frac{1}{4} + \frac{1}{8}\sqrt{3k+1}$.

Reference

[1] Vasile Cirtoaje, “The Equal Variable Method”, J. Inequal. Pure and Appl. Math., 8(1), 2007. Online: https://www.emis.de/journals/JIPAM/images/059_06_JIPAM/059_06.pdf