IMO 1987 Problem 3

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 4m00s

Problem

Let $x_1 , x_2 , \ldots , x_n$ be real numbers satisfying $x_1^2 + x_2^2 + \cdots + x_n^2 = 1$. Prove that for every integer $k \ge 2$ there are integers $a_1, a_2, \ldots a_n$, not all 0, such that $| a_i | \le k-1$ for all $i$ and

$|a_1x_1 + a_2x_2 + \cdots + a_nx_n| \le \frac{ (k-1) \sqrt{n} }{ k^n - 1 }$.

Exploration

Consider the family of all integer vectors $a=(a_1,\dots,a_n)$ with each $a_i$ in ${0,1,\dots,k-1}$. For each such vector, the quantity $S(a)=a_1x_1+\cdots+a_nx_n$ is a real number controlled by the Euclidean constraint $x_1^2+\cdots+x_n^2=1$. By Cauchy–Schwarz, $|S(a)|\le (k-1)\sqrt{n}$, so all such values lie in a bounded interval symmetric around $0$.

To obtain small nontrivial integer combinations, differences of two such vectors are natural, since if $a,b$ lie in this box then $c=a-b$ satisfies $|c_i|\le k-1$ and is not identically zero when $a\neq b$. The problem reduces to forcing two values $S(a)$ and $S(b)$ to be close.

A direct pigeonhole argument suggests ordering many such values and bounding the minimum gap. The main difficulty is ensuring the denominator $k^n-1$ appears correctly and that no extraneous factor remains in the final bound.

A refinement is to symmetrize the set by also including negatives of all vectors, which doubles the number of points and improves the pigeonhole bound sufficiently to match the stated inequality.

Problem Understanding

The problem concerns a unit vector $(x_1,\dots,x_n)$ in Euclidean space and asks for a nonzero integer vector $a$ with bounded coordinates such that the linear form $a\cdot x$ is small.

This is a Type D problem, requiring an explicit construction of such an integer vector together with a rigorous verification of the bound.

The key difficulty is to simultaneously control the size of the coefficients and force cancellation in the linear combination. The structure suggests a combinatorial pigeonhole argument in a finite set of integer vectors.

The claimed bound

$$\frac{(k-1)\sqrt{n}}{k^n-1}$$

indicates that $k^n$ objects are being compared inside an interval of length proportional to $(k-1)\sqrt{n}$.

Proof Architecture

The first lemma establishes a uniform bound $|a\cdot x|\le (k-1)\sqrt{n}$ for all integer vectors $a$ with $|a_i|\le k-1$.

The second lemma constructs a finite symmetric set $\mathcal{A}$ of integer vectors with $2k^n-1$ elements, each satisfying the coefficient bound.

The third lemma applies the one-dimensional pigeonhole principle to the values $S(a)$ for $a\in\mathcal{A}$, producing two distinct vectors $a,b$ such that $|S(a)-S(b)|$ is at most the required spacing.

The final step converts the difference $c=a-b$ into a nonzero integer vector satisfying $|c_i|\le k-1$ and the desired bound.

The most delicate step is the symmetric enlargement of the set to remove the factor $2$ in the denominator estimate.

Solution

Lemma 1

For any integers $a_1,\dots,a_n$ with $|a_i|\le k-1$, the inequality $|a_1x_1+\cdots+a_nx_n|\le (k-1)\sqrt{n}$ holds.

For each index $i$, the bound $|a_ix_i|\le (k-1)|x_i|$ holds, hence

$$|a_1x_1+\cdots+a_nx_n|\le \sum_{i=1}^n |a_ix_i|\le (k-1)\sum_{i=1}^n |x_i|.$$

Applying Cauchy–Schwarz to $(|x_1|,\dots,|x_n|)$ and $(1,\dots,1)$ yields

$$\sum_{i=1}^n |x_i|\le \sqrt{n(x_1^2+\cdots+x_n^2)}=\sqrt{n}.$$

Combining both inequalities gives the claim.

This establishes a uniform interval containment for all such linear forms, preventing uncontrolled growth of the set of values.

Lemma 2

Let $\mathcal{A}$ be the set of all vectors in $\mathbb{Z}^n$ with each coordinate in ${0,1,\dots,k-1}$ together with their negatives. Then $\mathcal{A}$ contains $2k^n-1$ distinct elements.

The set ${0,1,\dots,k-1}^n$ has $k^n$ elements. Negating each vector produces another set of $k^n$ vectors with coordinates in ${-(k-1),\dots,0}$. The only overlap occurs at the zero vector, so the total number of distinct elements is $2k^n-1$.

Every element of $\mathcal{A}$ satisfies $|a_i|\le k-1$ for all $i$ by construction.

This constructs a sufficiently large finite symmetric collection of admissible coefficient vectors.

Lemma 3

Let $S(a)=a_1x_1+\cdots+a_nx_n$. There exist distinct $a,b\in\mathcal{A}$ such that

$$|S(a)-S(b)|\le \frac{2(k-1)\sqrt{n}}{2k^n-1}.$$

By Lemma 1, every $S(a)$ with $a\in\mathcal{A}$ lies in the interval $[-(k-1)\sqrt{n},(k-1)\sqrt{n}]$, whose length equals $2(k-1)\sqrt{n}$. The set $\mathcal{A}$ contains $2k^n-1$ elements, hence $2k^n-1$ real numbers $S(a)$ in this interval.

Ordering these values increasingly produces $2k^n-1$ points in an interval of length $2(k-1)\sqrt{n}$. Among consecutive differences, at least one gap is at most

$$\frac{2(k-1)\sqrt{n}}{2k^n-1}.$$

This guarantees the existence of distinct $a,b\in\mathcal{A}$ satisfying the stated inequality.

This step converts a high-dimensional discrete set into a one-dimensional spacing argument, where the pigeonhole principle forces a close pair.

Completion of the construction

Let $c=a-b$. Each coordinate satisfies $|c_i|\le k-1$ since both $a_i$ and $b_i$ lie in ${-(k-1),\dots,k-1}$ with one of them being nonpositive and the other nonnegative, ensuring the difference stays within the same bound.

Moreover, $c\neq 0$ since $a\neq b$. Also,

$$c\cdot x = a\cdot x - b\cdot x,$$

$$|c\cdot x|=|S(a)-S(b)|\le \frac{2(k-1)\sqrt{n}}{2k^n-1}.$$

Finally,

$$\frac{2(k-1)\sqrt{n}}{2k^n-1}\le \frac{(k-1)\sqrt{n}}{k^n-1}$$

since $2k^n-1\ge 2(k^n-1)$. Therefore,

$$|c\cdot x|\le \frac{(k-1)\sqrt{n}}{k^n-1}.$$

This produces a nonzero integer vector with the required coordinate bound and inequality.

The constructed vector $c$ satisfies all conditions of the problem.

Verification of Key Steps

The bound $|a\cdot x|\le (k-1)\sqrt{n}$ follows independently from Cauchy–Schwarz applied to the absolute values of coordinates and the unit norm condition $x_1^2+\cdots+x_n^2=1$. Any attempt to replace this step with a coordinatewise maximum argument alone would fail because cancellations are not controlled without summation bounds.

The cardinality $2k^n-1$ is verified by checking that negation is an involution on the nonzero cube ${0,\dots,k-1}^n\setminus{0}$ and that no nonzero vector equals its own negative in this range. Omitting the zero-vector correction would overcount and invalidate the pigeonhole denominator.

The inequality comparison $\frac{2}{2k^n-1}\le \frac{1}{k^n-1}$ is confirmed by cross-multiplication, where the strict inequality $2k^n-1\ge 2(k^n-1)$ ensures monotonicity of reciprocals; neglecting the subtraction of $1$ would lead to a false equality assumption.

Alternative Approaches

A lattice-theoretic approach applies Minkowski’s convex body theorem to the cube ${a\in\mathbb{R}^n: |a_i|\le k-1}$ intersected with a slab ${|a\cdot x|\le \lambda}$, choosing $\lambda$ so that the volume exceeds $2^n$. This yields existence of a nonzero lattice point satisfying a similar bound.

Another approach uses Dirichlet approximation in higher dimensions by interpreting $x$ as defining a linear map $\mathbb{Z}^n\to\mathbb{R}$ and approximating $0$ by differences of $k$-ary digit vectors. The combinatorial pigeonhole argument is preferable because it avoids geometric measure arguments and produces the sharp constant directly through counting.