Kvant Math Problem 1278

For $n=2$, the conditions give $x_2=-x_1$ and $2x_1^2=1$, hence $x_1x_2=-\frac12\le-\frac12=-\frac1n$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m53s
Source on kvant.digital

Problem

There are $n$ real numbers $x_1$, $x_2$, $\ldots$, $x_n$ satisfying the conditions $x_1+x_2+\ldots+x_n=0$ and $x_1^2+x_2^2+\ldots+x_n^2=1$. Prove that $x_ix_j \le -\dfrac{1}{n}$ for some $i$ and $j$.

E. Stolov

Exploration

For $n=2$, the conditions give $x_2=-x_1$ and $2x_1^2=1$, hence $x_1x_2=-\frac12\le-\frac12=-\frac1n$. The statement holds.

For $n=3$, take $(a,a,-2a)$. Then $6a^2=1$, so $a^2=\frac16$. The negative products are $-2a^2=-\frac13$, exactly the required bound. This suggests that the constant $\frac1n$ may be sharp.

The conclusion asks for the existence of a sufficiently negative pair. Assume the contrary: every product satisfies

$$x_ix_j>-\frac1n \qquad (i\ne j).$$

Since

$$\left(\sum_{i=1}^n x_i\right)^2 = \sum_{i=1}^n x_i^2+2\sum_{i<j}x_ix_j,$$

the condition $\sum x_i=0$ converts information about pairwise products into information about the sum of squares. Because $\sum x_i^2=1$, we have

$$\sum_{i<j}x_ix_j=-\frac12.$$

The contradiction should come from comparing this exact value with the lower bound obtained from the assumption $x_ix_j>-\frac1n$.

There are $\frac{n(n-1)}2$ pairs. If each exceeds $-\frac1n$, then

$$\sum_{i<j}x_ix_j> -\frac1n\cdot\frac{n(n-1)}2 = -\frac{n-1}2.$$

For $n\ge3$, this lower bound is at least $-1$, which is not yet contradictory to $-\frac12$. The estimate is too weak.

A better idea is to use the exact identity

$$1=\sum x_i^2=-2\sum_{i<j}x_ix_j.$$

Under the contrary assumption,

$$1=-2\sum_{i<j}x_ix_j < -2\cdot\frac{n(n-1)}2\cdot\left(-\frac1n\right) = n-1.$$

This yields $1<n-1$. For $n\ge3$ this is true, not a contradiction.

The previous direction is wrong. Instead, suppose every pair satisfies

$$x_ix_j>-\frac1n.$$

Then

$$\sum_{i<j}x_ix_j>-\frac{n-1}{2}.$$

Combining with $\sum_{i<j}x_ix_j=-\frac12$ gives only

$$-\frac12>-\frac{n-1}{2},$$

which is false for $n\ge3$ and hence produces a contradiction immediately:

$$-\frac12=-\frac12\not> -\frac{n-1}{2}.$$

More carefully,

$$-\frac12=\sum_{i<j}x_ix_j>-\frac{n-1}{2}.$$

For $n\ge3$, the right-hand side is at most $-1$, so the inequality is actually true, not contradictory. Again no contradiction.

A different approach is needed.

The identity

$$1=\sum x_i^2 = -;2\sum_{i<j}x_ix_j$$

shows that the average value of the pairwise products equals

$$\frac{\sum_{i<j}x_ix_j}{\binom n2} = -\frac1{n(n-1)}.$$

The desired bound $-\frac1n$ is much stronger than the average. Thus a simple averaging argument cannot work.

Try separating positive and negative numbers. Let the positive numbers have sum $s$. Then the negative numbers have sum $-s$. Let

$$P=\sum_{x_i>0}x_i^2,\qquad N=\sum_{x_i<0}x_i^2.$$

Then $P+N=1$.

If $a$ is the largest positive number and $b$ is the most negative number, then $ab<0$. Since the positive numbers sum to $s$, we have $a\ge s/p$, where $p$ is the number of positive terms. Similarly, $|b|\ge s/q$, where $q$ is the number of negative terms. Hence

$$a|b|\ge \frac{s^2}{pq}.$$

Since $p+q\le n$, we have $pq\le \frac{n^2}{4}$, giving

$$a|b|\ge \frac{4s^2}{n^2}.$$

To obtain $a|b|\ge \frac1n$, it would suffice to show $s^2\ge \frac n4$, which is false in general.

Use Cauchy:

$$s^2\le pP,\qquad s^2\le qN.$$

Hence

$$\frac{s^2}{p}+\frac{s^2}{q}\le P+N=1.$$

Thus

$$s^2\le \frac{pq}{p+q}\le \frac{pq}{n}.$$

This goes in the opposite direction.

The previous estimates suggest using the largest positive number $a$ and the largest magnitude negative number $-b$ with $a,b>0$. From Cauchy,

$$P\le as,\qquad N\le bs.$$

Therefore

$$1=P+N\le (a+b)s.$$

Also $s\le pa$ and $s\le qb$. Hence

$$1\le (a+b)\min(pa,qb).$$

Assume for contradiction that every negative-positive product satisfies

$$ab<\frac1n.$$

Then $b<\frac1{na}$, and

$$1\le (a+b)\min!\left(pa,\frac q{na}\right).$$

This looks promising. Let $t=na^2$. Then

$$(a+b)\min(pa,qb) < \left(a+\frac1{na}\right)\min!\left(pa,\frac q{na}\right).$$

If $t\le \frac qp$, the expression equals

$$\left(a+\frac1{na}\right)pa = p\left(a^2+\frac1n\right) = \frac p n(t+1).$$

Since $t\le q/p$, this is at most

$$\frac pn\left(\frac qp+1\right) = \frac{p+q}{n} \le 1.$$

Strict inequality is preserved because $b<1/(na)$.

If $t\ge \frac qp$, the expression equals

$$\left(a+\frac1{na}\right)\frac q{na} = \frac q n\left(1+\frac1t\right) \le \frac q n\left(1+\frac pq\right) = \frac{p+q}{n} \le 1.$$

Again strict inequality holds.

Thus $1<1$, a contradiction. The crucial step is the estimate $P+N\le(a+b)s$.

Problem Understanding

We are given real numbers $x_1,\dots,x_n$ satisfying

$$x_1+\cdots+x_n=0, \qquad x_1^2+\cdots+x_n^2=1.$$

We must prove that at least one pair of indices $i,j$ satisfies

$$x_ix_j\le -\frac1n.$$

This is a Type B problem. The task is to prove the stated assertion.

The core difficulty is that the average pairwise product equals only $-\frac1{n(n-1)}$, much weaker than the required bound $-\frac1n$. A direct averaging argument cannot succeed. One must exploit simultaneously the conditions on the sum and on the sum of squares.

Proof Architecture

Let $p$ be the number of positive terms, $q$ the number of negative terms, and let $s$ be the sum of the positive terms; then the negative terms sum to $-s$.

Let $a$ be the largest positive term and $-b$ the smallest negative term, with $a,b>0$. Then $P\le as$ and $N\le bs$, where $P$ and $N$ are the sums of squares of the positive and negative terms respectively, because every positive term is at most $a$ and every negative term has absolute value at most $b$.

From $P+N=1$ it follows that $1\le(a+b)s$.

Since the sum of the positive terms equals $s$, we have $s\le pa$; similarly $s\le qb$.

Assume that every product of a positive and a negative term exceeds $-\frac1n$. Then $ab<\frac1n$.

Combining $1\le(a+b)s$ with $s\le\min(pa,qb)$ and $ab<\frac1n$, we derive

$$1<(a+\tfrac1{na})\min!\left(pa,\tfrac q{na}\right)\le1,$$

a contradiction.

The most delicate point is proving the final inequality

$$\left(a+\frac1{na}\right)\min!\left(pa,\frac q{na}\right)\le1$$

in all cases.

Solution

If $n=2$, then $x_2=-x_1$ and

$$2x_1^2=1.$$

Hence

$$x_1x_2=-x_1^2=-\frac12=-\frac1n.$$

The statement holds.

Assume henceforth that $n\ge3$.

Let $p$ be the number of positive terms and $q$ the number of negative terms. Since the sum of all numbers is $0$ and the sum of their squares is $1$, there is at least one positive term and at least one negative term. Thus $p,q\ge1$.

Let

$$s=\sum_{x_i>0}x_i.$$

Then

$$\sum_{x_i<0}x_i=-s.$$

Denote by

$$a=\max{x_i:x_i>0}, \qquad b=\max{-x_i:x_i<0}.$$

Thus $a>0$ and $b>0$.

Let

$$P=\sum_{x_i>0}x_i^2, \qquad N=\sum_{x_i<0}x_i^2.$$

Since every positive term is at most $a$,

$$P=\sum_{x_i>0}x_i^2 \le a\sum_{x_i>0}x_i = as.$$

Since every negative term has absolute value at most $b$,

$$N=\sum_{x_i<0}x_i^2 \le b\sum_{x_i<0}(-x_i) = bs.$$

Adding these inequalities gives

$$1=P+N\le(a+b)s.$$

Therefore

$$1\le(a+b)s. \tag{1}$$

The sum of the positive terms equals $s$, and there are $p$ of them, each not exceeding $a$. Hence

$$s\le pa. \tag{2}$$

Similarly,

$$s\le qb. \tag{3}$$

Suppose, toward a contradiction, that

$$x_ix_j>-\frac1n \qquad \text{for every }i,j. \tag{4}$$

In particular, for every positive term $u$ and every negative term $-v$,

$$-uv>-\frac1n,$$

so

$$uv<\frac1n.$$

Taking $u=a$ and $v=b$, we obtain

$$ab<\frac1n. \tag{5}$$

From (1), (2), and (3),

$$1\le(a+b)\min(pa,qb). \tag{6}$$

By (5),

$$b<\frac1{na}.$$

Hence

$$(a+b)\min(pa,qb) < \left(a+\frac1{na}\right) \min!\left(pa,\frac q{na}\right). \tag{7}$$

Set

$$t=na^2.$$

If $t\le \frac qp$, then

$$pa\le \frac q{na},$$

and therefore

$$\left(a+\frac1{na}\right) \min!\left(pa,\frac q{na}\right) = \left(a+\frac1{na}\right)pa = p\left(a^2+\frac1n\right) = \frac pn(t+1).$$

Since $t\le \frac qp$,

$$\frac pn(t+1) \le \frac pn\left(\frac qp+1\right) = \frac{p+q}{n} \le1. \tag{8}$$

If $t\ge \frac qp$, then

$$\frac q{na}\le pa,$$

and therefore

$$\left(a+\frac1{na}\right) \min!\left(pa,\frac q{na}\right) = \left(a+\frac1{na}\right)\frac q{na} = \frac qn\left(1+\frac1t\right).$$

Since $t\ge\frac qp$,

$$\frac1t\le\frac pq,$$

so

$$\frac qn\left(1+\frac1t\right) \le \frac qn\left(1+\frac pq\right) = \frac{p+q}{n} \le1. \tag{9}$$

Relations (8) and (9) show that

$$\left(a+\frac1{na}\right) \min!\left(pa,\frac q{na}\right) \le1.$$

Together with (6) and (7), this yields

$$1 \le (a+b)\min(pa,qb) < \left(a+\frac1{na}\right) \min!\left(pa,\frac q{na}\right) \le1,$$

which is impossible.

The contradiction shows that assumption (4) is false. Hence there exist indices $i$ and $j$ such that

$$x_ix_j\le-\frac1n.$$

This completes the proof.

∎

Verification of Key Steps

The estimate

$$1\le(a+b)s$$

comes from

$$P=\sum_{x_i>0}x_i^2\le as, \qquad N=\sum_{x_i<0}x_i^2\le bs.$$

A careless argument might replace these by equalities. Equality is generally false; only the upper bounds are needed. Since $P+N=1$, adding the inequalities gives the required relation.

The passage from the assumption

$$x_ix_j>-\frac1n$$

to

$$ab<\frac1n$$

uses the largest positive number $a$ and the largest absolute value $b$ among the negative numbers. Their product corresponds to one actual positive-negative pair, so the assumption applies directly. No extremal principle beyond this is involved.

The final case analysis depends on

$$t=na^2.$$

The two cases

$$t\le\frac qp, \qquad t\ge\frac qp$$

are exhaustive. In the first case the minimum equals $pa$; in the second it equals $\frac q{na}$. Reversing these choices would invalidate the computation. The inequalities

$$\frac pn(t+1)\le\frac{p+q}{n}, \qquad \frac qn\left(1+\frac1t\right)\le\frac{p+q}{n}$$

follow exactly from the corresponding assumptions on $t$.

Alternative Approaches

A different proof can be obtained through quadratic forms. Let $a$ be the largest positive term and $-b$ the smallest negative term. Assuming $ab<1/n$, one derives bounds on the positive and negative parts using Cauchy's inequality:

$$s^2\le pP,\qquad s^2\le qN.$$

Combining these with $P+N=1$ and optimizing under the restriction $ab<1/n$ leads again to a contradiction. The calculations are somewhat longer because one must eliminate several auxiliary variables.

The presented argument is preferable because it uses only the extremal positive and negative entries together with the elementary inequalities $P\le as$ and $N\le bs$. The contradiction emerges from a short optimization in a single variable $t=na^2$, making the structure of the proof transparent.