Kvant Math Problem 894

The previous proof contains critical errors in both parts.

kvantmathematicsolympiad

Verified: yes
Verdicts: PASS + PASS
Solve time: 36m39s
Source on kvant.digital

Problem

  1. The sum of five nonnegative numbers is equal to 1. Prove that they can be arranged around a circle so that the sum of the five pairwise products of adjacent numbers does not exceed $\dfrac15$.
  2. $n\ge4$ nonnegative numbers whose sum is equal to 1 are arranged around a circle. Prove that the sum of all $n$ pairwise products of adjacent numbers does not exceed $\dfrac14$.

S. B. Gashkov, A. N. Dranishnikov

Moscow Mathematical Olympiad (1984)

The previous proof contains critical errors in both parts. The odd case of Part 2 should be replaced entirely. The optimization in Part 1 should also be replaced by a different argument.

Exploration

Part 2 suggests looking for a reduction from a cycle with many vertices to a cycle with fewer vertices. Since the numbers are nonnegative and have fixed sum, a natural choice is to remove a smallest number and compare the adjacent product sum before and after the removal.

For Part 1, the statement is existential: we only need to show that some arrangement works. This makes averaging over all circular arrangements attractive. If the average adjacent product sum over all arrangements is at most $1/5$, then at least one arrangement must satisfy the required inequality.

Problem Understanding

For Part 2, let

$$ S=\sum_{i=1}^{n} a_i a_{i+1}, $$

where indices are taken modulo $n$ and

$$ a_1+\cdots+a_n=1. $$

We must prove

$$ S\le \frac14 $$

for every circular arrangement whenever $n\ge4$.

For Part 1, five given nonnegative numbers summing to $1$ must be arranged around a circle so that the adjacent product sum does not exceed $1/5$.

Proof Architecture

For Part 2, use induction on $n$. Choose a smallest number $m$. Remove its vertex and merge its two neighbors. The resulting cycle has one fewer vertex and the same total sum. A direct computation shows that the adjacent product sum cannot decrease under this operation. The induction then reduces everything to the case $n=4$.

For Part 1, average the adjacent product sum over all circular arrangements of the five numbers. Every unordered pair of numbers is adjacent in exactly half of all circular arrangements. Hence the average value equals

$$ \frac12\sum_{i<j}x_i x_j. $$

Using

$$ \sum_{i<j}x_i x_j =\frac{1-\sum x_i^2}{2} $$

and

$$ \sum x_i^2\ge\frac15, $$

the average is at most $1/5$. Therefore at least one arrangement has adjacent product sum at most $1/5$.

Solution

Part 2

We prove by induction on $n\ge4$ that

$$ S=\sum_{i=1}^{n} a_i a_{i+1}\le \frac14 . $$

For $n=4$,

$$ S=a_1a_2+a_2a_3+a_3a_4+a_4a_1. $$

Grouping terms gives

$$ S=(a_1+a_3)(a_2+a_4). $$

Since

$$ (a_1+a_3)+(a_2+a_4)=1, $$

we obtain

$$ S\le\frac14. $$

Assume now that the statement is true for cycles with $n-1$ vertices, where $n\ge5$.

Let $m=a_k$ be the smallest number. Denote its two neighbors by

$$ x=a_{k-1},\qquad y=a_{k+1}, $$

and denote the neighbors of $x$ and $y$ outside this triple by

$$ a=a_{k-2},\qquad b=a_{k+2}. $$

Construct a new cycle with $n-1$ vertices by deleting $m$ and replacing the adjacent vertices $x$ and $y$ by a single vertex of weight

$$ x+y. $$

The total sum of the numbers remains equal to $1$.

Let $S'$ be the adjacent product sum in the new cycle. The contributions unaffected by the local modification are the same in $S$ and $S'$.

The local contribution in the original cycle is

$$ ax+xm+my+yb. $$

The local contribution in the new cycle is

$$ a(x+y)+(x+y)b. $$

Hence

a(x+y)+(x+y)b-(ax+xm+my+yb). $$ After simplification, y(a-m)+x(b-m). $$

Since $m$ is the smallest of all numbers,

$$ a\ge m,\qquad b\ge m, $$

and therefore

$$ S'-S\ge0. $$

Thus

$$ S\le S'. $$

The new cycle has $n-1$ vertices and total sum $1$, so by the induction hypothesis,

$$ S'\le\frac14. $$

Consequently,

$$ S\le\frac14. $$

The induction is complete.

Part 1

Let the five numbers be

$$ x_1,x_2,x_3,x_4,x_5, \qquad x_1+\cdots+x_5=1. $$

Consider all circular arrangements of these five numbers. For each arrangement let $T$ be the sum of the five products of adjacent numbers.

We compute the average value of $T$ over all circular arrangements.

There are

$$ \binom52=10 $$

unordered pairs of numbers. In a circular arrangement there are exactly five adjacent pairs. By symmetry, every unordered pair is adjacent in the same number of arrangements. Since half of the $10$ possible pairs appear among the five edges of a cycle, each pair contributes with probability $1/2$.

Therefore

\frac12\sum_{i<j}x_i x_j. $$ Using \frac{(x_1+\cdots+x_5)^2-\sum_{i=1}^{5}x_i^2}{2}, $$

and $x_1+\cdots+x_5=1$, we get

\frac{1-\sum_{i=1}^{5}x_i^2}{4}. $$ By Cauchy, \frac15. $$

Hence

\frac15. $$ Since the average value of $T$ over all circular arrangements is at most $1/5$, at least one arrangement satisfies $$ T\le\frac15. $$ This proves the existence required in Part 1. Thus $$ \boxed{\text{For }n\ge4,\ \sum a_i a_{i+1}\le\frac14} $$ for every arrangement, and for five numbers summing to $1$ there exists an arrangement with adjacent product sum at most $$ \boxed{\frac15}. $$ ∎