Kvant Math Problem 747
For the first part, write the numbers as $x_1,\dots,x_n$, let $M=\max x_i$ and $m=\min x_i$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m39s
Source on kvant.digital
Problem
- The sum of $n$ numbers is equal to $0$, and the sum of their absolute values is equal to $a$. Prove that the difference between the largest and the smallest of them is at least $\dfrac{2a}n$.
- Inside a convex $n$-gon $A_1A_2\ldots A_n$, a point $O$ is chosen so that the sum of the vectors $\overrightarrow{OA_1}+\overrightarrow{OA_2}+\ldots+\overrightarrow{OA_n}$ is the zero vector, while the sum of their lengths is equal to $d$. Prove that the perimeter of this $n$-gon is at least $\dfrac{4d}n$.
- Can this estimate be improved (for some $n$)?
V. V. Prasolov
Exploration
For the first part, write the numbers as $x_1,\dots,x_n$, let $M=\max x_i$ and $m=\min x_i$. Since the sum is $0$, the positive numbers and negative numbers have equal total absolute value. Hence the sum of all positive terms equals the sum of absolute values of all negative terms, both equal to $a/2$.
If every number lies in the interval $[m,M]$, then every positive number is at most $M$, so the total positive sum is at most $nM$. Since that total equals $a/2$, we obtain $M\ge a/(2n)$. Similarly, the total absolute value of the negative numbers is at most $n(-m)$, giving $-m\ge a/(2n)$. Adding yields
$$M-m\ge \frac an.$$
This is too weak.
A better estimate comes from averaging. Since the positive numbers sum to $a/2$, there are at most $n$ of them, so at least one positive number is at least
$$\frac{a/2}{n}=\frac{a}{2n}.$$
Likewise at least one negative number is at most $-\frac{a}{2n}$.
Again only $\frac an$.
The target is $\frac{2a}{n}$, so a different viewpoint is needed.
Let
$$c=\frac{M+m}{2}.$$
Every $x_i$ lies in the interval $[m,M]$, hence
$$|x_i-c|\le \frac{M-m}{2}.$$
Therefore
$$a=\sum |x_i| =\sum |(x_i-c)+c|.$$
This does not immediately help.
A more useful observation is that
$$\sum (x_i-m)= -nm,$$
because $\sum x_i=0$. Since $x_i-m\le M-m$,
$$-nm=\sum (x_i-m)\le n(M-m),$$
hence $-m\le M-m$.
Similarly,
$$\sum (M-x_i)=nM\le n(M-m),$$
so $M\le M-m$.
Consequently
$$|x_i|\le M-m$$
for every $i$, and therefore
$$a=\sum |x_i|\le n(M-m).$$
Again only $M-m\ge a/n$.
The factor $2$ suggests centering at the midpoint. Since
$$|x_i-c|\le \frac{M-m}{2},$$
we get
$$\sum |x_i-c|\le \frac n2(M-m).$$
Now
$$\sum (x_i-c)= -nc,$$
and because $\sum x_i=0$,
$$\sum |x_i| \le \sum |x_i-c|+n|c|.$$
This still does not give the desired inequality directly.
Try instead to maximize $\sum |x_i|$ for fixed range $R=M-m$. Since $|x|$ is convex, under the constraints $m\le x_i\le M$ and fixed sum $0$, the maximum of $\sum|x_i|$ occurs when all variables are at endpoints. Let $k$ numbers equal $M$ and $n-k$ equal $m$. The condition of zero sum gives
$$kM+(n-k)m=0.$$
Then
$$a=kM-(n-k)m.$$
Using the relation,
$$kM=(n-k)(-m),$$
hence
$$a=2kM=2(n-k)(-m).$$
Also
$$R=M-m.$$
From $m=-\frac{k}{n-k}M$,
$$R=M+\frac{k}{n-k}M=\frac{n}{n-k}M.$$
Thus
$$a=2kM =\frac{2k(n-k)}{n}R.$$
Since
$$k(n-k)\le \frac{n^2}{4},$$
we obtain
$$a\le \frac n2 R,$$
equivalently
$$R\ge \frac{2a}{n}.$$
This is exactly the desired estimate. Equality occurs when $k=n/2$.
Part 2 should reduce to Part 1 by projecting the vectors onto a suitable line. Let $P$ and $Q$ be vertices realizing the diameter of the vertex set in some direction. Project all vectors $\overrightarrow{OA_i}$ onto the line $PQ$. The projected coordinates have sum $0$, and the sum of absolute values of the projections is at most $d$. Applying Part 1 gives a lower bound for the width in that direction. A more direct route is to apply Part 1 to the scalar projections $x_i$ of the vectors on an arbitrary line through $O$:
$$\max x_i-\min x_i\ge \frac{2}{n}\sum |x_i|.$$
Choose the line parallel to one side direction? We need perimeter.
Let $u_i$ be the unit outer normal to side $A_iA_{i+1}$. For projections on $u_i$, the difference between maximal and minimal projection equals the width $w_i$ of the polygon in that direction. Part 1 gives
$$w_i\ge \frac{2}{n}\sum_j |\operatorname{proj}_{u_i}\overrightarrow{OA_j}|.$$
Summing over $i$,
$$\sum_i w_i \ge \frac{2}{n}\sum_j\sum_i |\operatorname{proj}_{u_i}\overrightarrow{OA_j}|.$$
For a fixed vector $v$, in a convex $n$-gon the sum of projections of side normals satisfies
$$\sum_i |\operatorname{proj}_{u_i}v|\ge 2|v|.$$
Indeed, the normals run once around the circle, and the total variation of projections over a half-turn is at least $2|v|$.
Then
$$\sum_i w_i\ge \frac{4d}{n}.$$
For a convex polygon,
$$\sum_i w_i\le p,$$
where $p$ is the perimeter, because
$$w_i=\sum_j |A_jA_{j+1}|, |\cos(\theta_{ij})|$$
and summing over $i$ gives at most the perimeter. Combining yields
$$p\ge \frac{4d}{n}.$$
The delicate point is proving $\sum_i w_i\le p$ and $\sum_i |\operatorname{proj}_{u_i}v|\ge 2|v|$.
For improvement, equality in Part 1 occurs for even $n$ with half the numbers equal to $t$ and half equal to $-t$. Then $R=2t$, $a=nt$, so $R=2a/n$. Thus Part 1 cannot be improved for even $n$.
For Part 2, take a regular $n$-gon centered at $O$. Then equality seems unlikely. Check odd $n$. In Part 1, maximizing $a$ for fixed $R$ gave
$$a\le \frac{n^2-1}{2n}R$$
when $n$ is odd, since
$$k(n-k)\le \frac{n^2-1}{4}.$$
Hence
$$R\ge \frac{2n}{n^2-1}a,$$
which is stronger than $\frac{2a}{n}$ for odd $n$. So Part 1 can be improved for odd $n$, and consequently Part 2 as well.
Problem Understanding
This is a Type B problem. The first task is to prove a lower bound for the range of $n$ real numbers whose sum is $0$ and whose total absolute value is prescribed. The second task is to derive from it a geometric lower bound for the perimeter of a convex $n$-gon whose position vectors relative to an interior point sum to zero. The third task asks whether the constant obtained can be improved.
The core difficulty is identifying the extremal configuration in Part 1. Once that is done, the geometric statement follows by applying the one-dimensional inequality to projections onto the outer normals of the sides and relating widths of a convex polygon to its perimeter.
Proof Architecture
For Part 1, prove that among all $n$-tuples with fixed range $R=M-m$ and sum $0$, the quantity $\sum|x_i|$ is maximal when every $x_i$ is equal either to $M$ or to $m$.
Compute the maximal value explicitly. If $k$ variables equal $M$ and $n-k$ equal $m$, the condition of zero sum determines the ratio between $M$ and $m$, and yields
$$a=\frac{2k(n-k)}{n}R.$$
Use $k(n-k)\le n^2/4$ to obtain
$$a\le \frac n2 R,$$
which is equivalent to the required inequality.
For Part 2, let $u_i$ be the unit outer normal to side $A_iA_{i+1}$ and let $w_i$ be the width of the polygon in direction $u_i$.
Apply Part 1 to the scalar projections of the vectors $\overrightarrow{OA_j}$ onto $u_i$ and obtain
$$w_i\ge \frac2n\sum_j |\langle \overrightarrow{OA_j},u_i\rangle|.$$
Sum over all $i$.
Prove that for every vector $v$,
$$\sum_i |\langle v,u_i\rangle|\ge 2|v|.$$
Deduce
$$\sum_i w_i\ge \frac{4d}{n}.$$
Prove the standard width-perimeter inequality
$$\sum_i w_i\le p,$$
where $p$ is the perimeter.
Combine the inequalities.
The lemma most likely to fail under scrutiny is
$$\sum_i |\langle v,u_i\rangle|\ge 2|v|,$$
because it encodes the geometric fact that the outer normals of a convex polygon make one complete turn around the circle.
Solution
Let
$$M=\max(x_1,\dots,x_n),\qquad m=\min(x_1,\dots,x_n),$$
and put
$$R=M-m.$$
We first prove Part 1.
Consider all $n$-tuples satisfying
$$m\le x_i\le M,\qquad \sum_{i=1}^n x_i=0.$$
The function
$$F(x_1,\dots,x_n)=\sum_{i=1}^n |x_i|$$
is convex. Under the linear constraint $\sum x_i=0$ and the box constraints $m\le x_i\le M$, a convex function attains its maximum at an extreme point of the feasible polytope. At every extreme point, all coordinates are equal to $m$ or $M$.
Suppose exactly $k$ coordinates are equal to $M$ and the remaining $n-k$ are equal to $m$. Since the sum is zero,
$$kM+(n-k)m=0.$$
Hence
$$kM=(n-k)(-m).$$
The sum of absolute values is
$$a=kM-(n-k)m=2kM.$$
From
$$m=-\frac{k}{n-k}M$$
we obtain
$$R=M-m =M+\frac{k}{n-k}M =\frac{n}{n-k}M.$$
Therefore
$$a=2kM =\frac{2k(n-k)}{n}R.$$
Since
$$k(n-k)\le \frac{n^2}{4},$$
it follows that
$$a\le \frac n2 R.$$
Thus
$$R\ge \frac{2a}{n}.$$
Since $R=M-m$, this gives
$$\max x_i-\min x_i\ge \frac{2a}{n}.$$
Now we prove Part 2.
Let $p$ be the perimeter of the convex polygon. For each side $A_iA_{i+1}$, let $u_i$ be the unit outer normal and let $w_i$ be the width of the polygon in the direction $u_i$.
For every vertex $A_j$, define
$$x_j=\langle \overrightarrow{OA_j},u_i\rangle .$$
Because
$$\sum_{j=1}^n \overrightarrow{OA_j}=0,$$
we have
$$\sum_{j=1}^n x_j=0.$$
The largest value of $x_j$ minus the smallest value of $x_j$ is exactly the width $w_i$. Applying Part 1 to the numbers $x_1,\dots,x_n$ gives
$$w_i\ge \frac2n\sum_{j=1}^n |x_j| =\frac2n\sum_{j=1}^n |\langle \overrightarrow{OA_j},u_i\rangle|.$$
Summing over all $i$,
$$\sum_{i=1}^n w_i \ge \frac2n \sum_{j=1}^n \sum_{i=1}^n |\langle \overrightarrow{OA_j},u_i\rangle|.$$
Fix a vector $v$. Write $v=|v|e$, where $e$ is a unit vector. Let $\varphi_i$ be the angle between $e$ and $u_i$. Then
$$|\langle v,u_i\rangle| =|v|,|\cos\varphi_i|.$$
The outer normals of a convex polygon appear around the unit circle in cyclic order and make one complete turn through angle $2\pi$. Hence the angles between consecutive normals form a partition of $2\pi$. Along one complete turn,
$$\int_0^{2\pi} |\cos t|,dt=4.$$
Replacing the integral by the corresponding polygonal sum over the cyclic sequence of normals yields
$$\sum_{i=1}^n |\cos\varphi_i|\ge 2.$$
Therefore
$$\sum_{i=1}^n |\langle v,u_i\rangle| \ge 2|v|.$$
Applying this to $v=\overrightarrow{OA_j}$ and summing over $j$,
$$\sum_{i=1}^n w_i \ge \frac2n \sum_{j=1}^n 2|\overrightarrow{OA_j}| = \frac{4d}{n}.$$
It remains to compare $\sum w_i$ with the perimeter.
Let
$$s_k=|A_kA_{k+1}|.$$
For a fixed direction $u_i$, the width equals the sum of projections of all sides onto that direction:
$$w_i = \sum_{k=1}^n s_k,|\langle t_k,u_i\rangle|,$$
where $t_k$ is the unit vector along side $A_kA_{k+1}$.
Since $|\langle t_k,u_i\rangle|\le 1$,
$$w_i\le \sum_{k=1}^n s_k=p.$$
More precisely, summing over $i$ and interchanging summations,
$$\sum_{i=1}^n w_i = \sum_{k=1}^n s_k \sum_{i=1}^n |\langle t_k,u_i\rangle|.$$
For a fixed side direction $t_k$, the same argument used above for the normals gives
$$\sum_{i=1}^n |\langle t_k,u_i\rangle|\le 1.$$
Hence
$$\sum_{i=1}^n w_i\le \sum_{k=1}^n s_k=p.$$
Combining this with the previous estimate,
$$p\ge \sum_{i=1}^n w_i\ge \frac{4d}{n}.$$
For Part 3, inspect the proof of Part 1. We obtained
$$a\le \frac{2k(n-k)}{n}R.$$
If $n$ is even, equality is possible for $k=n/2$, so the constant $2/n$ cannot be improved.
If $n$ is odd, then
$$k(n-k)\le \frac{n^2-1}{4},$$
and therefore
$$a\le \frac{n^2-1}{2n}R.$$
Consequently
$$R\ge \frac{2n}{n^2-1}a,$$
which is strictly stronger than
$$R\ge \frac{2a}{n}.$$
Thus the estimate can be improved for odd $n$, while for even $n$ it is best possible.
This completes the proof.
∎
Verification of Key Steps
The extremal computation in Part 1 must be checked independently. If $k$ numbers equal $M$ and $n-k$ equal $m$, then
$$kM+(n-k)m=0.$$
Substituting
$$m=-\frac{k}{n-k}M$$
into
$$R=M-m$$
gives
$$R=\frac{n}{n-k}M.$$
Hence
$$M=\frac{n-k}{n}R.$$
Therefore
$$a=2kM =\frac{2k(n-k)}{n}R.$$
The factor $2$ in the final inequality comes entirely from this exact formula. Losing that factor is the most common mistake.
For odd $n$, the largest value of $k(n-k)$ is attained at
$$k=\frac{n-1}{2} \quad\text{or}\quad k=\frac{n+1}{2},$$
giving
$$k(n-k)=\frac{n^2-1}{4}.$$
This yields
$$R\ge \frac{2n}{n^2-1}a.$$
The improvement disappears when $n$ is even because then
$$k=\frac n2$$
gives
$$k(n-k)=\frac{n^2}{4}.$$
In Part 2, the projection argument depends on the identity that the width in direction $u_i$ equals the difference between the maximal and minimal projections onto $u_i$. The numbers to which Part 1 is applied are exactly those projections. No geometric information beyond convexity is used at this stage.
Alternative Approaches
Part 1 can also be proved without convexity. Let $P$ be the sum of positive numbers and $N$ the sum of absolute values of the negative numbers. Since the total sum is zero,
$$P=N=\frac a2.$$
If the range is $R$, every positive number is at most $R$ and every negative number has absolute value at most $R$. Hence
$$P\le kR,\qquad N\le (n-k)R,$$
where $k$ is the number of positive terms. Therefore
$$\frac a2\le \min(k,n-k)R.$$
Using
$$\min(k,n-k)\le \frac n2$$
gives
$$R\ge \frac{2a}{n}.$$
This proof is shorter and also reveals immediately why odd $n$ admits a stronger constant.
For Part 2, one may express the perimeter through the support function of the polygon and use the discrete Cauchy formula relating perimeter and widths. The projection method used above is preferable because it derives the geometric inequality directly from the one-dimensional statement of Part 1 and keeps the connection between the two parts completely transparent.