A Geometric Inequality?

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

A Geometric Inequality?

G H J

Reveal topic tags

Geometry inequality

L

G H BBookmark kLocked kLocked NReply

Source: China TST 2007, Problem 5

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1270 posts

April

#1 h Dec 29, 2008, 6:29 AM • 2 Y

Y by Adventure10, Mango247

Let $x_1, \ldots, x_n$ be $n>1$ real numbers satisfying $A=\left |\sum^n_{i=1}x_i\right |\not =0$ and $B=\max_{1\leq i<j\leq n}|x_j-x_i|\not =0$ . Prove that for any $n$ vectors $\vec{\alpha_i}$ in the plane, there exists a permutation $(k_1, \ldots, k_n)$ of the numbers $(1, \ldots, n)$ 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|.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

606 posts

#2 h Jul 8, 2016, 3:45 AM • 2 Y

Y by Adventure10, Mango247

We do a weighting trick. Let $\pi$ denote a permutation $(\pi(1), \pi(2), \dots, \pi(n))$ , and let $\sum_{\pi}$ sum over all permutations of $\{1, \dots, n\}.$ Assume that $|\vec{\alpha_1}| \ge 1.$ Then it suffices to show the problem with the RHS replaced with $\frac{AB}{2A+B}.$ 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|$ for some real weights $w_\pi$ for all permutations $\pi.$

Now choose the weights $w_{\pi}$ such that $\sum_\pi w_\pi x_{\pi(i)} = \begin{cases} 1 \textnormal{ if } i = 1 \\ 0 \textnormal{ otherwise} \\ \end{cases}.$ 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},$ so our goal is now to minimize $\sum_\pi |w_\pi|$ given the previous system of equations.

My next claim is a duality claim. Let $c_1, \dots, c_n$ 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|} .$ 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|} .$ 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 $x_1 \le \dots \le x_n$ , and $\sum x_i > 0.$ Also assume that $c_1 \le \dots \le c_n$ , 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}.$ This statement has to be true, because it is the same as the original problem, except with the vectors $\alpha_i$ replaced by real numbers $c_i$ ! 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),$ because $x_1 \le \dots \le x_n$ and $c_1 \le \dots \le c_n.$

Lemma 1: If $c_n > 0$ and $c_1 \le 0$ , we are done.

This is because $\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.$ 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|,$ as desired.

Lemma 2: If $0 < c_1 \le \dots \le c_n$ , we are also done.

It suffices to consider the case where are $c_i$ are positive by symmetry. Also assume WLOG that $c_n = 1$ , so $\max_i |c_i| = 1.$ 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}.$ Consider a real $0 \le d \le 1.$ 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}).$ I will show that the last expression will be at least $\frac{AB}{2A+B},$ which will finish. Note that the sequence $\{dx_1 - (1-d)x_n, dx_2 - (1-d)x_{n-1}, \dots, dx_n - (1-d)x_1\}$ is an increasing sequence. Since we have no restrictions on $c_1, \dots, c_{n-1}$ other than they are between in the range $[0, 1]$ , we can smooth them to all be the same value, since we want to minimize the previous quantity. After we smooth to $c_1 = \dots = c_{n-1}$ , we can then smooth all of them to equal $0$ or $1$ , 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).$ ow we make our choice of $d$ . A good choice is $2d-1 = \frac{B}{2A+B} \implies d = \frac{A+B}{2A+B}.$ Then clearly $0 \le d \le 1.$ To show that $\min((2d-1)A, (x_1+x_n)d - x_1) \ge \frac{AB}{2A+B}$ , it suffices to show that $(x_1+x_n)\frac{A+B}{2A+B} - x_1 \ge \frac{AB}{2A+B}$ $\frac{A+B}{2A+B}x_n - \frac{A}{2A+B}x_1 \ge \frac{AB}{2A+B}$ $(A+B)x_n - Ax_1 \ge AB = A(x_n-x_1) \Leftrightarrow Bx_n \ge 0,$ which is true as we assumed that $\sum x_i > 0 \implies x_n > 0$ . So we're done.

Remark: There must be an easier way... I think the beginning manipulation was all fairly roundabout, so I am hoping that there is a more direct solution.

This post has been edited 2 times. Last edited by mathocean97, Jul 9, 2016, 4:18 AM
Reason: Added a remark.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4071 posts

#3 h Jul 8, 2016, 1:49 PM • 1 Y

Y by Adventure10

mathocean97 wrote:

Essentially, by the duality of linear programming, one can show that equality holds, i.e. $\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|} .$ 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)

Can you show me the last step,plz

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

209 posts

rterte

#4 h Nov 20, 2016, 1:39 PM • 1 Y

Y by Adventure10

Any other solution for this problem?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2311 posts

#5 h Nov 21, 2016, 3:27 AM • 9 Y

Y by atmchallenge, Ankoganit, ThE-dArK-lOrD, anantmudgal09, rterte, muffin_cowee, enhanced, Siddharth03, Adventure10

WLOG assume that $\left | x_n - x_1 \right| = \max_{1\leq i<j\leq n} \left| x_j-x_i \right| = B,$ $\left| \vec{\alpha_n} - \vec{\alpha_1} \right| = \max_{1\leq i<j\leq n} \left| \vec{\alpha_j} - \vec{\alpha_i} \right|$ and let $\begin{align*} \vec{\beta} = x_1 \vec{\alpha_1} + x_2 \vec{\alpha_2} + \dots + x_{n-1} \vec{\alpha_{n-1}} + x_n \vec{\alpha_n} \\ \vec{\gamma} = x_n \vec{\alpha_1} + x_2 \vec{\alpha_2} + \dots + x_{n-1} \vec{\alpha_{n-1}} + x_1 \vec{\alpha_n} &. \end{align*}$ Then $\mathbf{M} = \max_{\substack{\{ k_1, \dots, k_n \} \\ = \{ 1, 2, \dots, n \}} } \left | \sum_{i=1}^{n}x_{k_i}\vec{\alpha_i} \right | \geq \frac{1}{2} \left( \left| \vec{\beta} \right| + \left| \vec{\gamma} \right| \right) \geq \frac{1}{2} \left| \vec{\gamma} - \vec{\beta} \right| = \frac{B}{2} \left| \vec{\alpha_n} - \vec{\alpha_1} \right|.$
Let $\left| \vec{\alpha_k} \right| = \max _{1\leq i\leq n}\left|\vec{\alpha_i} \right|$ ( $k \in \mathbb{N}, 1 \leq k \leq n$ ) and $\left| \vec{\alpha_n} - \vec{\alpha_1} \right| = t \left| \vec{\alpha_k} \right|$ ( $t \in \mathbb{R}, 0 \leq t \leq 2$ ), then we get
$\mathbf{M} \geq \frac{Bt}{2} \left| \vec{\alpha_k} \right| \qquad \qquad \qquad (\dagger).$
On the other hand, let $\vec{\varsigma_i} = x_i \vec{\alpha_1} + x_{i+1} \vec{\alpha_2} + \dots + x_n \vec{\alpha_{n-i+1}} + x_1 \vec{\alpha_{n-i+2}}+ \dots + x_{i-1} \vec{\alpha_n},$ then $\mathbf{M} \geq \frac{1}{n} \sum_{i=1}^{n} \left| \vec{\varsigma_i} \right| \geq \frac{1}{n} \left| \sum_{i=1}^{n} \vec{\varsigma_i} \right| = \frac{A}{n} \left| n\vec{\alpha_k} - \sum_{j \neq k} \left( \vec{\alpha_k} - \vec{\alpha_j} \right)\right|,$ so $\mathbf{M} \geq \frac{A}{n} \left( n \left| \vec{\alpha_k} \right| - \sum_{j \neq k} \left| \vec{\alpha_k} - \vec{\alpha_j} \right| \right) \geq \frac{A}{n} \left( n \left| \vec{\alpha_k} \right| - \left( n-1 \right) \left| \vec{\alpha_n} - \vec{\alpha_1} \right| \right) = \left( A - \frac{\left(n-1\right) At }{n} \right) \left| \vec{\alpha_k} \right| \qquad (\ddagger).$ Combining $(\dagger)$ and $(\ddagger)$ we conclude that $\mathbf{M} \geq \max \left\{ \frac{Bt}{2}, \left( A - \frac{\left(n-1\right) At }{n} \right) \right\} \left| \vec{\alpha_k} \right| \geq \left( \frac{\frac{Bt}{2} \cdot \frac{\left(n-1\right)A}{n} + \left( A - \frac{\left(n-1\right) At }{n} \right) \cdot \frac{B}{2}}{\frac{\left(n-1\right)A}{n} + \frac{B}{2}} \right) \left| \vec{\alpha_k} \right|.$ i.e. there exists a permutation $\left( k_1, \dots, k_n \right )$ of the numbers $\left(1, \dots, n \right )$ such that $\left |\sum_{i=1}^{n} x_{k_i}\vec{\alpha_i}\right | \geq \frac{AB}{\frac{2\left(n-1 \right)}{n}A+B} \max_{1\leq i\leq n}\left|\vec{\alpha_i}\right|.$

This post has been edited 1 time. Last edited by TelvCohl, Nov 21, 2016, 4:44 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a