AoPS Academy
which satisfy 
![$ \frac{a+b+c}{3} \ge \sqrt[10]{\frac{a^3+b^3+c^3}{3}}$](http://latex.artofproblemsolving.com/c/d/a/cdae05ad34239366b0dd3921243522c711b6ae58.png)
method, I can assum 
![$ \frac{2x+\frac{1}{x^2}}{3} \ge \sqrt[10]{ \frac{2x^3+ \frac{1}{x^6}}{3}} $](http://latex.artofproblemsolving.com/c/d/4/cd481672bee1e87d8c97ac623436e0ec75cfa73a.png)
are given such that 
. Prove the inequality 
, let 
denote the smallest possible value of 
where 
are sets such that 
and 
whenever 
. Determine for each positive integer .
denote a permutation 
, and let 
sum over all permutations of 
Assume that 
Then it suffices to show the problem with the RHS replaced with 
Consider the following equation. ![\[ \left(\sum_\pi |w_\pi| \right) \max_{\pi} \left| \sum_{i = 1}^n x_{\pi(i)} \vec{\alpha_i} \right| \ge \sum_{\pi} |w_{\pi}| \left| \sum_{i = 1}^n x_{\pi(i)} \vec{\alpha_i} \right| \ge \left| \sum_\pi w_\pi \sum_{i = 1}^n x_{\pi(i)} \vec{\alpha_i} \right| = \left| \sum_{i = 1}^n \vec{\alpha_i} \sum_\pi w_\pi x_{\pi(i)} \right| \]](http://latex.artofproblemsolving.com/7/c/c/7cc5a39024e4dd85d194c4d726275acb7d05c138.png)
for some real weights 
for all permutations 
such that ![\[ \sum_\pi w_\pi x_{\pi(i)} = \begin{cases} 1 \textnormal{ if } i = 1 \\ 0 \textnormal{ otherwise} \\ \end{cases}. \]](http://latex.artofproblemsolving.com/3/8/e/38e59d1e46062223ff11ea1a32b3ee458283c75e.png)
Substituting this in, we have that ![\[ \max_{\pi} \left| \sum_{i = 1}^n x_{\pi(i)} \vec{\alpha_i} \right| \ge \left(\sum_\pi |w_\pi| \right)^{-1}, \]](http://latex.artofproblemsolving.com/d/c/f/dcf2c8dbd673554fca7bb4fe1605ffcebf486563.png)
so our goal is now to minimize 
given the previous system of equations.
be real numbers. Then we know that ![\[ \sum_{i = 1}^n c_i \sum_\pi w_\pi x_{\pi(i)} = c_1 \implies \sum_\pi |w_\pi| \ge \frac{|c_1|}{\max_\pi \left| \sum_{i = 1}^n c_i x_{\pi(i)}\right|} . \]](http://latex.artofproblemsolving.com/a/a/5/aa5b842eb488b01f27b41b63616d499f91ffa518.png)
Essentially, by the duality of linear programming, one can show that equality holds, i.e. ![\[ \min \sum_\pi |w_\pi| = \max_{\substack{c_1, \dots, c_n \in \mathbb{R} \\ \sum |c_i| > 0}} \frac{|c_1|}{\max_{\pi} \left|\sum_{i = 1}^n c_i x_{\pi(i)}\right|} . \]](http://latex.artofproblemsolving.com/3/5/2/3521d34f65d397a8b89576ab3ebf40e52ba78122.png)
So we have reduced it to an optimization problem on the right hand side of the equation. The denominator can be one of two things, by using the rearrangement inequality. Assume without loss of generality that 
, and 
Also assume that 
, and instead we show that ![\[ \max_{\substack{c_1, \dots, c_n \in \mathbb{R} \\ \sum |c_i| > 0}} \frac{ \max_i |c_i|}{\max_{\pi} \left|\sum_{i = 1}^n c_i x_{\pi(i)}\right|} \le \frac{2A+B}{AB}. \]](http://latex.artofproblemsolving.com/3/1/6/316bfda5f361ee3fe116eda28c9415bd4d045302.png)
This statement has to be true, because it is the same as the original problem, except with the vectors 
replaced by real numbers 
! So we have strictly simplified the problem. Now, looking at the denominator, it equals ![\[ \max\left(\sum c_i x_i, -\sum c_i x_{n+1-i}\right), \]](http://latex.artofproblemsolving.com/6/e/e/6eeb868629c6da10c77711dd38f143cb56ce9751.png)
because and 
and 
, we are done.![\[ \sum c_i x_i-\sum c_i x_{n+1-i} = \sum_{i = 1}^{n/2} (c_{n+1-i} - c_i)(x_{n+1-i}-x_i) \ge (c_n - c_1)B \ge \max_i |c_i| B. \]](http://latex.artofproblemsolving.com/2/3/8/2389b488a9b34d67e050cd9b7c9bb1fd673ebce6.png)
Therefore, ![\[ \max\left(\sum c_i x_i, -\sum c_i x_{n+1-i} \right) \ge \frac{B}{2} \max_i |c_i| \ge \frac{AB}{2A+B} \max_i |c_i|, \]](http://latex.artofproblemsolving.com/3/7/3/373edf66b66f930df66c5be25e34184b28220baa.png)
as desired.
, we are also done. are positive by symmetry. Also assume WLOG that 
, so 
We want to show that ![\[ \max\left(\sum c_i x_i, -\sum c_i x_{n+1-i} \right) \ge \frac{AB}{2A+B}. \]](http://latex.artofproblemsolving.com/3/6/c/36ca9546b3fd062e5057785c8a00dcecc7370e5d.png)
Consider a real 
Consider the sum ![\[ d\sum c_i x_i - (1-d) \sum c_i x_{n+1-i} = \sum c_i (dx_i - (1-d)x_{n+1-i}). \]](http://latex.artofproblemsolving.com/0/4/f/04f737030840c743902241a61a35f07591d358b6.png)
I will show that the last expression will be at least 
which will finish. Note that the sequence 
is an increasing sequence. Since we have no restrictions on 
other than they are between in the range ![$[0, 1]$](http://latex.artofproblemsolving.com/a/b/1/ab178d831a786b92cb4c9ddc2d33578223036f98.png)
, we can smooth them to all be the same value, since we want to minimize the previous quantity. After we smooth to 
, we can then smooth all of them to equal 
or 
, as the expression is linear in those variables. Therefore, ![\[ \sum c_i (dx_i - (1-d)x_{n+1-i}) \ge \min((2d-1)\sum x_i, dx_n - (1-d)x_1) = \min((2d-1)A, (x_1+x_n)d - x_1). \]](http://latex.artofproblemsolving.com/6/3/6/636a28bd922fb0a9def3f7825e3874ceb4a1d636.png)
ow we make our choice of 
. A good choice is 
Then clearly To show that 
, it suffices to show that ![\[ (x_1+x_n)\frac{A+B}{2A+B} - x_1 \ge \frac{AB}{2A+B} \]](http://latex.artofproblemsolving.com/2/7/7/277202008d72b2de68531015de1b51c4024154dd.png)
![\[ \frac{A+B}{2A+B}x_n - \frac{A}{2A+B}x_1 \ge \frac{AB}{2A+B} \]](http://latex.artofproblemsolving.com/9/3/c/93c16031343e3018c67d03c3ee1eadd2e9db0226.png)
![\[ (A+B)x_n - Ax_1 \ge AB = A(x_n-x_1) \Leftrightarrow Bx_n \ge 0, \]](http://latex.artofproblemsolving.com/9/6/2/9624d828c4681c89abcfd9c51441d48cde1714b6.png)
which is true as we assumed that 
. So we're done.
![\[ \min \sum_\pi |w_\pi| = \max_{c_1, \dots, c_n \in \mathbb{R}} \frac{|c_1|}{\max_{\pi} \left|\sum_{i = 1}^n c_i x_{\pi(i)}\right|} . \]](http://latex.artofproblemsolving.com/a/e/8/ae894e45652386a6d0c61bbb38b4f8ce433fba5e.png)
So we have reduced it to an optimization problem on the right hand side of the equation. The denominator can be one of two things, by using the rearrangement inequality. (Finish to come)
and let 
Then 
(
) and 
(
), then we get
then 
so 
Combining 
and 
we conclude that 
i.e. there exists a permutation 
of the numbers 
such that 
in natural numbers m and n.
be 
real numbers satisfying 
and 
.
vectors 
in the plane, there exists a permutation 
of the numbers 
such that ![\[ \left |\sum_{i=1}^nx_{k_i}\vec{\alpha_i}\right | \geq \dfrac{AB}{2A+B}\max_{1\leq i\leq n}|\alpha_i|.\]](http://latex.artofproblemsolving.com/b/7/8/b782ff3d60196f42d88ef81fd27c23bbaf5c8656.png)
