Hard Inequality

Lemma 1: There exists $x_i > 4$ .

Proof: From the problem, we have $4(x_1^2 + x_2^2 + \ldots + x_k^2 ) < 2(x_1 + x_2 + \ldots + x_k) < x_1^3 + x_2^3 + \ldots +x_k^3$ The lemma follows directly. Thus, proven.

Let $p(x) = 2x^2 - x$ , and $q(x)=x^3-2x$ . Also, let $f(x)=\frac{q(x)}{p(x)}$ .

We have $p(x) < 0 \; \forall x \in \left ( 0, \frac{1}{2} \right )$ , decreasing for $x \in \left ( 0, \frac{1}{4} \right )$ , and increasing for $x > \frac{1}{4}$ .

We also have $q(x) < 0 \; \forall x \in \left (-\infty, -\sqrt{2} \right ) \cup \left (0, \sqrt{2} \right )$ , decreasing for $x \in \left (\frac{-\sqrt{2}}{\sqrt{3}}, \frac{\sqrt{2}}{\sqrt{3}} \right )$ , and increasing for all other values of $x$ . Thus, $q(x)$ is decreasing in the interval $\left (0, \frac{1}{2} \right )$ .

From here, we gather that $f(x) > 0 \; \forall x \in \left (0, \frac{1}{2} \right ) \cup \left (\sqrt{2}, \infty \right )$ and is increasing for $x \neq 0, \frac{1}{2}$ .

From the problem, we know there exists $x_1 \leq x_2 \leq \ldots \leq x_k$ such that $p(x_1) + p(x_2) + \ldots +p(x_k) < 0$ and $q(x_1) + q(x_2) + \ldots + q(x_k) > 0$ .

Lemma 2: $x_{k-1} < \frac{1}{2}$ .

Proof: Suppose not. Then, we can construct $x_{0} > x_{k}$ such that $p(x_{k-1})+p(x_k) = p(x_{0})$ , and the sum $q(x_i)$ will not decrease since $q(x_0) = f(x_0) p(x_0) = f(x_0) p(x_k) + f(x_0) p(x_{k-1}) \geq f(x_k) p(x_k) + f(x_{k-1}) p(x_{k-1}) = q(x_{k-1}) + q(x_k)$ . Thus, we can decrease $k$ by replacing $x_{k-1}$ and $x_k$ with $x_0$ , which is a contradiction. Thus, this lemma is proven.

If $x_i \in \left ( \frac{1}{4} , \frac {1}{2} \right )$ , then we can replace $x_i$ with $\frac{1}{2} - x_i$ . This operation changes $p(x_i) = 2x_i^2 - x_i$ to $p \left ( \frac{1}{2} - x_i \right ) = 2 \left ( \frac{1}{2} - x_i \right )^2 - \frac{1}{2} + x_i = \frac{1}{2} - 2x_i + 2x_i^2 - \frac{1}{2} + x_i = 2x_i^2 - x_i = p(x_i)$ , so the sum $p(x_i)$ doesn’t change. The operation also changes $q(x_i)$ in such a way that the sum doesn’t decrease (since $q(x)$ is decreasing in the interval $\left ( 0, \frac{1}{2} \right )$ . Thus, we can assume that $x_1, x_2, \ldots, x_{k-1} \in \left ( 0, \frac{1}{4} \right ]$ .

Lemma 3: Let $a, b, c, d$ satisfy $0 < a < b < c < d \leq \frac{1}{4}$ , and $p(a)+p(d)=p(b)+p(c)$ . Then we have $q(a) + q(d) < q(b) + q(c)$ .

Proof: In this interval, $p(x)$ is decreasing from before, so we have $p(c) - p(d) = p(a) - p(b) > 0$ . Thus, it suffices to prove $\frac{q(c)-q(d)}{p(c)-p(d)} > \frac{q(a)-q(b)}{p(a)-p(b)}$ .

Denote $F(x, y) = \frac{q(x)-q(y)}{p(x)-p(y)}$ . Then we have $\begin{aligned} F(x,y) &= \frac{q(x)-q(y)}{p(x)-p(y)}\\ &= \frac{x^3 - y^3 - 2x + 2y}{2x^2 - 2y^2 - x + y}\\ &= \frac{x^2 + xy + y^2 - 2}{2x + 2y - 1}\\ &= f(x+y) + \frac{xy}{1-2(x+y)} \end{aligned}$ Thus, it follows that if $x$ and $y$ both increase, then $F(x, y)$ also increases. Since $c$ and $d$ are greater than $a$ and $b$ , we have $F(c, d) > F(a, b)$ . Thus, this lemma is proven.

Let $P$ be the arithmetic mean of $p(x_1), p(x_2), \ldots , p(x_{k-1})$ . If $p(x_i) > P$ , then there exists $j$ such that $p(x_j) < P$ . Thus, we can replace $x_i$ and $x_j$ with $x_{i_1}$ and $x_{j_1}$ respectively such that $p(x_i) + p(x_j) = p(x_{i_1}) + p(x_{j_1})$ and either of $p(x_{i_1})$ or $p(x_{j_1})$ is equal to $P$ . This follows from the continuity of $p$ on the interval $\left ( 0 \frac{1}{4} \right ]$ .

From Lemma 3 , it follows that the sum $q(x_i)$ will increase. We inductively apply this operation on $P$ until all $p(x_i)$ are equal to $P$ .

Therefore, we can set $x_1 = x_2 = \ldots x_{k-1} = u \leq \frac{1}{2}, x_k = v > 4$ (From Lemma 1 ).

Thus, what is left is for us to determine the minimum $n=k-1$ such that $2(nu^2 + v^2) < nu + v$ and $2 (nu + v) < nu^3 + v^3$ .

We rewrite these inequalities in the form $\frac{2v^2 - v}{u - 2u^2} < n < \frac{v^3 - 2v}{2u - u^3}$ . Hence, $f(v) > f(u)$ .

We will now attempt to determine the minimum value the expression $\frac{2v^2 - v}{u - 2u^2}$ can take under the given conditions (This will give the lower bound for $n$ ).

We reduce $v$ until we reach the value at which $f(v) = f(u)$ . Since $f(u) > f(0) = 2 = f(4)$ , then the new value of $v$ is greater than $4$ . Thus, the number $\frac{2v^2 - v}{u - 2u^2}$ decreases.

Now, $u$ and $v$ are the roots of the quadratic equation $x^2 - 2 = t(2x - 1)$ , where $t=f(u)$ , so $u+v = 2t$ , which implies $v = 2f(u) - u = \frac{4 - u}{1 - 2u}$ .

Substituting this into the expression $\frac{2v^2 - v}{u - 2u^2}$ , we get $g(u) = \frac{7(4-u)}{u(1-2u)^3}$ . The numerator of $g’(u)$ is $-14 (3u^2 - 16u + 2)$ , so $g’$ vanishes at the point $u_0 = \frac{8 - \sqrt{58}}{3} \in \left ( 0 , \frac{1}{4} \right ]$ , so this is the minimum point.

Therefore, $n > g(u_0) = 514.16…$ , so $n \geq 515$ , which implies $k \geq 516$ .

This can be achieved if we let $x_1 = x_2 = \ldots x_{515} = \frac{1}{8}$ , and $x_{516} = 5.169$ (which can be achieved by substituting the values back into the formulae we have achieved).

Thus, proven.

This problem was one of the problems from the 2006 Tournament of Towns Contests.