Kvant Math Problem 527
Denote
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m33s
Source on kvant.digital
Problem
Let $x_1$, $x_2$, $\ldots$, $x_n$ be real numbers, $0\le x_i\le1$. Prove that the quantity $$x_1+x_2+\ldots+x_{n-1}+x_n-x_1x_2-x_2x_3-\ldots-x_{n-1}x_n-x_nx_1$$ does not exceed
- 1 when $n=3$;
- 2 when $n=4$;
- $\left[\dfrac n2\right]$ for any $n\ge3$.
V. Batyrev, 10th-grade student
Exploration
Denote
$$S=\sum_{i=1}^n x_i-\sum_{i=1}^n x_i x_{i+1},$$
where indices are taken modulo $n$.
For $n=3$,
$$S=x_1+x_2+x_3-x_1x_2-x_2x_3-x_3x_1.$$
If $x_1=x_2=x_3=\frac12$, then $S=\frac34$. If $x_1=1,x_2=0,x_3=0$, then $S=1$. Thus the bound $1$ looks plausible.
For $n=4$, taking $x_1=x_3=1$ and $x_2=x_4=0$ gives
$$S=2.$$
Hence the proposed bound is attained.
For general $n$, the alternating choice
$$1,0,1,0,\ldots$$
gives $S=\lfloor n/2\rfloor$. Thus the stated bound is sharp.
The expression is linear in each variable separately. Fix all variables except $x_k$. Then
$$S=(1-x_{k-1}-x_{k+1})x_k+\text{constant}.$$
Hence, as a function of $x_k$, it is affine. Its maximum on the interval $[0,1]$ is attained at an endpoint. Repeating this for all variables suggests that a maximum is attained when every $x_i$ equals $0$ or $1$.
Once the variables are reduced to $0$ and $1$, the problem becomes combinatorial. If $x_i\in{0,1}$, then
$$x_i-x_i x_{i+1}=x_i(1-x_{i+1}),$$
so
$$S=\sum_{i=1}^n x_i(1-x_{i+1}).$$
Each summand equals $1$ exactly when a $1$ is followed by a $0$ on the cycle. Thus $S$ counts transitions $1\to0$.
On a cycle, every such transition must be separated by at least one vertex carrying $1$ and at least one vertex carrying $0$. Consequently the number of transitions cannot exceed $\lfloor n/2\rfloor$. This appears to be the crucial step; it must be justified carefully.
Problem Understanding
We are given numbers $x_1,\dots,x_n$ satisfying $0\le x_i\le1$, and
$$S=x_1+\cdots+x_n-(x_1x_2+x_2x_3+\cdots+x_nx_1).$$
The task is to prove that $S\le1$ for $n=3$, $S\le2$ for $n=4$, and in general
$$S\le \left\lfloor\frac n2\right\rfloor .$$
This is a Type B problem. The statement to be proved is given in advance.
The core difficulty is to pass from arbitrary real variables in $[0,1]$ to a discrete extremal problem and then determine the largest possible value of the resulting combinatorial quantity.
Proof Architecture
First, prove that for fixed values of all variables except $x_k$, the expression $S$ is affine in $x_k$; hence a maximum of $S$ over the cube $[0,1]^n$ is attained at a vertex, that is, when every $x_i\in{0,1}$.
Second, prove that for $0$-$1$ variables,
$$S=\sum_{i=1}^n x_i(1-x_{i+1}),$$
so $S$ equals the number of cyclic transitions $1\to0$.
Third, prove that if there are $m$ such transitions on a cycle of length $n$, then $2m\le n$; hence $m\le\lfloor n/2\rfloor$.
Finally, identify configurations attaining $m=\lfloor n/2\rfloor$, namely alternating $1$'s and $0$'s.
The most delicate point is the proof that the number of $1\to0$ transitions on a cycle cannot exceed $\lfloor n/2\rfloor$.
Solution
Let
$$S=\sum_{i=1}^n x_i-\sum_{i=1}^n x_i x_{i+1},$$
where $x_{n+1}=x_1$.
Consider $S$ as a function of a single variable $x_k$, with all other variables fixed. The terms containing $x_k$ are
$$x_k-x_{k-1}x_k-x_kx_{k+1},$$
so
$$S=(1-x_{k-1}-x_{k+1})x_k+C,$$
where $C$ does not depend on $x_k$.
Hence $S$ is an affine function of $x_k$. An affine function on the interval $[0,1]$ attains its maximum at one of the endpoints $0$ or $1$.
Take a point of $[0,1]^n$ at which $S$ is maximal. Replacing $x_1$ by one of the endpoints $0$ or $1$ does not decrease $S$. Then, keeping the new value of $x_1$ fixed, replace $x_2$ by $0$ or $1$ without decreasing $S$, and continue in the same way. After finitely many steps we obtain a point with all coordinates in ${0,1}$ at which the value of $S$ is at least as large as the original maximum. Therefore some maximum of $S$ is attained for a $0$-$1$ vector.
It remains to consider only the case $x_i\in{0,1}$.
For such variables,
$$S=\sum_{i=1}^n \bigl(x_i-x_i x_{i+1}\bigr) =\sum_{i=1}^n x_i(1-x_{i+1}).$$
Each summand $x_i(1-x_{i+1})$ equals $1$ precisely when
$$x_i=1,\qquad x_{i+1}=0,$$
and equals $0$ otherwise. Thus $S$ is exactly the number of indices $i$ for which a $1$ is followed by a $0$ on the cycle.
Let this number be $m$.
Choose one index from each transition $1\to0$, namely the position carrying the $1$. These chosen positions are distinct. Also, the positions immediately following them, which carry $0$, are distinct. Hence every transition contributes at least two distinct vertices of the cycle, one carrying $1$ and one carrying $0$.
Since the cycle has only $n$ vertices,
$$2m\le n.$$
Therefore
$$m\le \left\lfloor\frac n2\right\rfloor.$$
Because $S=m$, we obtain
$$S\le \left\lfloor\frac n2\right\rfloor.$$
For $n=3$,
$$S\le \left\lfloor\frac32\right\rfloor=1.$$
For $n=4$,
$$S\le \left\lfloor\frac42\right\rfloor=2.$$
Thus all three assertions follow from the general estimate.
This completes the proof.
∎
Verification of Key Steps
The reduction to $0$-$1$ variables depends on the fact that $S$ is affine in each variable separately. For fixed $x_{k-1}$ and $x_{k+1}$,
$$S=(1-x_{k-1}-x_{k+1})x_k+C.$$
If the coefficient is positive, the maximum on $[0,1]$ occurs at $x_k=1$; if it is negative, at $x_k=0$; if it is zero, every value gives the same result. Thus replacing $x_k$ by an endpoint never decreases $S$.
The interpretation of $S$ as a transition count uses the identity
$$x_i-x_i x_{i+1}=x_i(1-x_{i+1}).$$
For $0$-$1$ values there are four possibilities:
$$(0,0),(0,1),(1,1),(1,0).$$
The expression equals $0,0,0,1$ respectively. Hence each summand records exactly one type of adjacent pair, namely $1\to0$.
The inequality $2m\le n$ requires care. If a vertex carries $1$ and starts a transition $1\to0$, then the next vertex carries $0$. Distinct transitions have distinct starting vertices, and their following vertices are also distinct. Consequently every transition occupies a pair of different vertices. No vertex can belong simultaneously to the $1$-part and the $0$-part of two transitions. Hence at least $2m$ vertices are needed, yielding $2m\le n$.
Alternative Approaches
A different proof starts from
$$x_i-x_i x_{i+1}\le \frac12\bigl(x_i+1-x_{i+1}\bigr).$$
Indeed,
$$\frac12\bigl(x_i+1-x_{i+1}\bigr)-x_i(1-x_{i+1}) =\frac12(1-x_i)(1-x_{i+1})+\frac12x_i x_{i+1}\ge0.$$
Summing over $i$ gives
$$S\le \frac12\sum_{i=1}^n (x_i+1-x_{i+1}) =\frac n2.$$
This immediately yields $S\le n/2$, which is sufficient for even $n$.
For odd $n$, one may combine this estimate with the fact that equality in the pointwise inequality requires $(x_i,x_{i+1})=(1,0)$. Such pairs cannot occur around an odd cycle at every edge, so equality is impossible; hence $S<n/2$. Since $S$ attains its maximum at a $0$-$1$ vector, the maximum is an integer and therefore does not exceed $\lfloor n/2\rfloor$.
The main proof is preferable because it converts the problem into a transparent counting statement and simultaneously identifies the extremal configurations.