Given an integer $ n > 3.$ Let $ a_{1},a_{2},\cdots,a_{n}$ be real numbers satisfying $ min |a_{i} - a_{j}| = 1, 1\le i\le j\le n.$ Find the minimum value of $ \sum_{k = 1}^n|a_{k}|^3.$
Problem
Source: Chinese National Olympiad 2009 P4
Tags: inequalities, symmetry, function, algebra, polynomial, absolute value, inequalities proposed
10.01.2009 21:44
WLOG let $ a_1 < a_2 < \dots < a_n$. Then using the given condition we obtain $ a_{i + 1}\ge a_i + 1$ for $ i = 1,2,\dots,n - 1$. Therefore $ a_i\ge a_1 + i - 1$ for all $ i$. Hence \[ \sum_{i = 1}^n|a_i|^3 = \frac 12\sum_{i = 1}^n(|a_i|^3 + |a_{n - i + 1}|^3) \ge \frac 12\sum_{i = 1}^n(|a_1 + i - 1|^3 + |a_1 + n - i|^3). \] But note that \begin{align*} & |a_1 + i - 1|^3 + |a_1 + n - i|^3 \\ = \, & (|a_1 + i - 1| + |a_1 + n - i|)(|a_1 + i - 1|^2 - |a_1 + i - 1|\cdot |a_1 + n - i| + |a_1 + n - i|^2). \end{align*} Now for the minimum of the right side we must have $ |a_1 + i - 1| = |a_1 + n - i|$, e.g. \[ - (a_1 + i - 1) = a_1 + n - i\Leftrightarrow a_1 = - \frac {n - 1}{2}. \] Thus the required minimum is \[ \sum_{i = 1}^n|i - 1 - \frac {n - 1}{2}|^3 = \sum_{i = 1}^n|i - \frac {n + 1}{2}|^3 = \{\begin{array}{c}\,\frac {n^2(n - 1)^2}{32},\text{ for even }n, \ \ \frac {(n - 1)^2(n + 1)^2}{32},\text{ for odd }n.\ \end{array} \]
12.01.2009 11:14
And could you explain what happens if a1 is negative. Then the inequality between ai and a1+i+1 wont necessary be true if we take the module.
12.01.2009 13:13
I don't see any problem when $ a_1$ is negative; could you please explain?
12.01.2009 15:42
Notice that any two numbers among $ a_1, \ldots, a_n$ are at distance at least $ 1$, and also notice that moving any two consecutive numbers closer together can only decrease the result. So we may assume that the numbers $ a_1, \ldots, a_n$ are $ t - \tfrac{n-1}{2}, \ldots, t + \tfrac{n-1}{2}$ for some real $ t$. Also notice that if $ |2t| > 1$ we may transfer the endpoint of the sequence that is largest in absolute value to the other end and reduce the result; so we may assume $ |t| \leq \tfrac12$. In addition, because of symmetry, we may assume that $ t$ is nonnegative. Thus for odd $ n = 2k + 1$ we need to find the obtainable minimum of \[ f(t) = t^3 + \sum_{i = 1}^{k}\left(i - t\right)^3 + \left(i + t\right)^3 \] and because the function is increasing (a polynomial with only positive coefficients) in $ t$, the minimum is at $ t = 0$. Similarly, when $ n = 2k$ is even, the sum is \[ g(t) = \sum_{i = 1}^{k}\left(i - \frac12 - t\right)^3 + \left(i - \frac12 + t\right)^3 \] and also the minimum is at $ t = 0$. So the minimum is $ f(0) = \tfrac{(n^2 - 1)^2}{32}$ for odd $ n$ and $ g(0) = \tfrac{n^2 (n^2 - 2)}{32}$ for even $ n$.
12.01.2009 20:33
Well 2>-3 but 3>2
13.01.2009 13:58
I'm sorry but I don't understand anything you are trying to say. Note that I did NOT put modulus in $ a_i\ge a_1 + i - 1$. And $ \min\{|a_i - a_j|\} = 1$ holds for all $ i\neq j$ as well so I don't see any problem.
06.05.2015 05:42
Quick outline-ish proof of a slicker way than smoothing: If you arrange $a_1<a_2<...a_n$ increasing and do $2b_k=a_k-a_{n+1-k}$, you get the new sequence has sum of cubes of absolute values at most as large while maintaining the condition (to check that it maintains the condition, it's just triangle inequality and Holder's). The new sequence has $b_k+b_{n+1-k}$, so it's easy to finish and get the answer. If n is odd the middle element is $0$, and something $r$ elements later or earlier has magnitude at least $r$. If $n$ is even the middle two elements have magnitude at least $\frac {1} {2}$, the next outermost $2$ have magnitudes at least $\frac {3} {2}$, and so on.