IMO 1966 Problem 5
Let
Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 8m43s
Problem
Solve the system of equations $$ |a_1-a_2|x_2+|a_1-a_3|x_3+|a_1-a_4|x_4=1 $$ $$ |a_2-a_1|x_1+|a_2-a_3|x_3+|a_2-a_4|x_4=1 $$ $$ |a_3-a_1|x_1+|a_3-a_2|x_2+|a_3-a_4|x_4=1 $$ $$ |a_4-a_1|x_1+|a_4-a_2|x_2+|a_4-a_3|x_3=1 $$ where $a_1, a_2, a_3, a_4$ are four different real numbers.
Exploration
Let
$$d_{ij}=|a_i-a_j|.$$
The system can be written as
$$\sum_{j\ne i} d_{ij}x_j=1 \qquad (i=1,2,3,4).$$
Since the coefficients are symmetric, the first idea is to subtract equations. If the numbers $a_i$ are ordered, the absolute values disappear and differences of coefficients become very simple.
Assume
$$a_1<a_2<a_3<a_4.$$
Then
$$d_{12}=a_2-a_1,\quad d_{13}=a_3-a_1,\quad d_{14}=a_4-a_1,$$
and similarly for the others.
Subtracting the first equation from the second gives
$$(a_2-a_1)x_1-(a_2-a_1)x_2+(a_1-a_2)x_3+(a_1-a_2)x_4=0,$$
hence
$$x_1+x_3+x_4=x_2+x_3+x_4,$$
so $x_1=x_2$.
Trying the subtraction of the second and third equations yields
$$x_1+x_2+x_4=x_1+x_2+x_4,$$
which suggests $x_2=x_3$. Continuing should give
$$x_1=x_2=x_3=x_4.$$
If all unknowns are equal to a common value $t$, then the first equation becomes
$$(d_{12}+d_{13}+d_{14})t=1.$$
For the chosen ordering,
$$d_{12}+d_{13}+d_{14} =(a_2-a_1)+(a_3-a_1)+(a_4-a_1).$$
This depends on $i$, so equal variables cannot satisfy all four equations unless a special relation holds. Hence the conjecture that all variables are equal must be checked carefully.
Recomputing the subtraction more systematically is necessary. Let
$$E_i:\quad \sum_{j\ne i} d_{ij}x_j=1.$$
For $E_2-E_1$,
$$d_{12}x_1-d_{12}x_2+(d_{23}-d_{13})x_3+(d_{24}-d_{14})x_4=0.$$
Under the ordering,
$$d_{23}-d_{13}=-(a_2-a_1),\qquad d_{24}-d_{14}=-(a_2-a_1),$$
so
$$x_1-x_2-x_3-x_4=0.$$
Similarly,
$$E_3-E_2:\quad x_1+x_2-x_3-x_4=0,$$
and
$$E_4-E_3:\quad x_1+x_2+x_3-x_4=0.$$
Solving these three relations gives
$$x_1=x_4,\qquad x_2=0,\qquad x_3=0.$$
Substituting into any equation then yields
$$d_{14}x_1=1,$$
hence
$$x_1=x_4=\frac1{a_4-a_1}.$$
This candidate satisfies all equations. The core insight is that ordering the $a_i$ turns every difference of equations into a linear relation whose coefficients are all equal up to sign.
Problem Understanding
We are given four distinct real numbers $a_1,a_2,a_3,a_4$ and a linear system in four unknowns $x_1,x_2,x_3,x_4$. The coefficients are the pairwise distances $|a_i-a_j|$.
The task is to determine all solutions of the system. This is a Type A problem, because a complete characterization of the solution set is required.
The mathematical objects involved are a $4\times4$ linear system whose diagonal entries are absent and whose off-diagonal entries are absolute differences of the given real numbers.
The main difficulty is the presence of absolute values. A direct attack on the system produces many coefficients. The useful structure appears only after ordering the $a_i$, which converts all absolute values into ordinary differences and makes the equations highly dependent.
The answer will be
$$x_2=x_3=0, \qquad x_1=x_4=\frac1{\max(a_i)-\min(a_i)}.$$
After relabeling so that $a_1<a_2<a_3<a_4$, this becomes
$$x_2=x_3=0, \qquad x_1=x_4=\frac1{a_4-a_1}.$$
Intuitively, only the two extreme points matter. The equations force the middle variables to vanish, and the remaining two variables are determined by the distance between the smallest and largest $a_i$.
Proof Architecture
We first reorder the indices so that
$$a_1<a_2<a_3<a_4.$$
The proof uses the following claims.
Lemma 1. Subtracting consecutive equations yields
$$x_1-x_2-x_3-x_4=0,$$
$$x_1+x_2-x_3-x_4=0,$$
$$x_1+x_2+x_3-x_4=0.$$
The reason is that, under the chosen ordering, every coefficient difference equals either $a_{k+1}-a_k$ or its negative.
Lemma 2. Every solution of the three relations in Lemma 1 satisfies
$$x_2=x_3=0,\qquad x_1=x_4.$$
This follows by elementary elimination.
Lemma 3. Any solution of the original system satisfies
$$x_1=x_4=\frac1{a_4-a_1}.$$
Substituting the relations from Lemma 2 into any equation leaves a single unknown.
The hardest direction is proving that no other solutions exist. Lemma 1 is the most delicate part because an incorrect sign in the coefficient differences would lead to a wrong linear relation.
Solution
Arrange the indices so that
$$a_1<a_2<a_3<a_4.$$
Since the numbers are distinct, such an ordering exists.
Let $E_i$ denote the $i$-th equation:
$$E_i:\qquad \sum_{j\ne i}|a_i-a_j|x_j=1.$$
Lemma 1
The equations $E_2-E_1$, $E_3-E_2$, and $E_4-E_3$ are respectively
$$x_1-x_2-x_3-x_4=0,$$
$$x_1+x_2-x_3-x_4=0,$$
$$x_1+x_2+x_3-x_4=0.$$
Proof
Subtract $E_1$ from $E_2$:
$$|a_1-a_2|x_1-|a_1-a_2|x_2 +\bigl(|a_2-a_3|-|a_1-a_3|\bigr)x_3 +\bigl(|a_2-a_4|-|a_1-a_4|\bigr)x_4=0.$$
Because
$$a_1<a_2<a_3<a_4,$$
we have
$$|a_2-a_3|-|a_1-a_3| =(a_3-a_2)-(a_3-a_1) =-(a_2-a_1),$$
and
$$|a_2-a_4|-|a_1-a_4| =(a_4-a_2)-(a_4-a_1) =-(a_2-a_1).$$
Since $|a_1-a_2|=a_2-a_1$, division by the positive number $a_2-a_1$ gives
$$x_1-x_2-x_3-x_4=0.$$
Next, subtract $E_2$ from $E_3$:
$$(|a_3-a_1|-|a_2-a_1|)x_1 +|a_2-a_3|x_2 -|a_2-a_3|x_3 +\bigl(|a_3-a_4|-|a_2-a_4|\bigr)x_4=0.$$
Using
$$(a_3-a_1)-(a_2-a_1)=a_3-a_2,$$
and
$$(a_4-a_3)-(a_4-a_2)=-(a_3-a_2),$$
division by $a_3-a_2>0$ yields
$$x_1+x_2-x_3-x_4=0.$$
Finally, subtract $E_3$ from $E_4$:
$$(|a_4-a_1|-|a_3-a_1|)x_1 +(|a_4-a_2|-|a_3-a_2|)x_2 +|a_3-a_4|x_3 -|a_3-a_4|x_4=0.$$
Since
$$(a_4-a_1)-(a_3-a_1)=a_4-a_3,$$
and
$$(a_4-a_2)-(a_3-a_2)=a_4-a_3,$$
division by $a_4-a_3>0$ gives
$$x_1+x_2+x_3-x_4=0.$$
The lemma is proved. ∎
This establishes all linear relations forced by differences of consecutive equations; skipping the explicit coefficient computations would risk an incorrect sign pattern.
Lemma 2
Every solution of the relations in Lemma 1 satisfies
$$x_2=x_3=0, \qquad x_1=x_4.$$
Proof
Subtract
$$x_1-x_2-x_3-x_4=0$$
from
$$x_1+x_2-x_3-x_4=0.$$
The result is
$$2x_2=0,$$
hence
$$x_2=0.$$
Subtract
$$x_1+x_2-x_3-x_4=0$$
from
$$x_1+x_2+x_3-x_4=0.$$
The result is
$$2x_3=0,$$
hence
$$x_3=0.$$
Substituting $x_2=x_3=0$ into
$$x_1+x_2+x_3-x_4=0$$
gives
$$x_1=x_4.$$
The lemma is proved. ∎
This establishes that the middle variables vanish; solving the full four-equation system directly would obscure this structure.
Lemma 3
Any solution of the original system satisfies
$$x_1=x_4=\frac1{a_4-a_1}.$$
Proof
By Lemma 2,
$$x_2=x_3=0, \qquad x_1=x_4.$$
Substitute these relations into the first equation:
$$|a_1-a_4|x_4=1.$$
Because $a_4>a_1$,
$$(a_4-a_1)x_4=1,$$
so
$$x_4=\frac1{a_4-a_1}.$$
Since $x_1=x_4$,
$$x_1=\frac1{a_4-a_1}.$$
The lemma is proved. ∎
This establishes the only possible value of the remaining variables; using a different equation gives the same result because the system is consistent.
We now verify that the obtained quadruple is indeed a solution.
Take
$$x_2=x_3=0, \qquad x_1=x_4=\frac1{a_4-a_1}.$$
The first equation becomes
$$|a_1-a_4|\frac1{a_4-a_1}=1.$$
Since $a_4>a_1$, this equals $1$.
The second equation becomes
$$|a_2-a_1|\frac1{a_4-a_1} + |a_2-a_4|\frac1{a_4-a_1}.$$
Because
$$(a_2-a_1)+(a_4-a_2)=a_4-a_1,$$
its value is $1$.
The third equation is verified similarly:
$$(a_3-a_1)+(a_4-a_3)=a_4-a_1.$$
The fourth equation becomes
$$|a_4-a_1|\frac1{a_4-a_1}=1.$$
Hence all four equations are satisfied.
Thus every solution must be
$$x_2=x_3=0, \qquad x_1=x_4=\frac1{a_4-a_1},$$
after ordering $a_1<a_2<a_3<a_4$.
Equivalently, for the original labeling,
$$x_i=x_j=\frac1{\max(a_k)-\min(a_k)}$$
for the indices corresponding to the minimum and maximum of the four numbers, while the remaining two variables are $0$.
$$\boxed{;x_{\min}=x_{\max}=\frac1{\max(a_i)-\min(a_i)},\qquad x_{\text{other}}=0;}$$
Verification of Key Steps
The first delicate step is the derivation of
$$x_1-x_2-x_3-x_4=0.$$
Starting from $E_2-E_1$, the coefficient of $x_3$ is
$$(a_3-a_2)-(a_3-a_1)=a_1-a_2.$$
The coefficient of $x_4$ is
$$(a_4-a_2)-(a_4-a_1)=a_1-a_2.$$
Both are negative multiples of $a_2-a_1$. Missing either sign would incorrectly produce $x_1=x_2$.
The second delicate step is solving the three linear relations. Writing them as
$$\begin{aligned} x_1-x_2-x_3-x_4&=0,\ x_1+x_2-x_3-x_4&=0,\ x_1+x_2+x_3-x_4&=0, \end{aligned}$$
the first two differ only in the sign of $x_2$, giving $2x_2=0$. The last two differ only in the sign of $x_3$, giving $2x_3=0$. Any shortcut that combines all three equations simultaneously can hide an algebraic mistake.
The third delicate step is the verification of the second and third original equations. After substitution,
$$\frac{|a_2-a_1|+|a_2-a_4|}{a_4-a_1} = \frac{(a_2-a_1)+(a_4-a_2)}{a_4-a_1} =1.$$
The identity relies on $a_2$ lying between $a_1$ and $a_4$. Without the chosen ordering, the simplification would not be justified.
Alternative Approaches
A different method is to write the system in matrix form $Mx=\mathbf 1$, where $M$ is the symmetric matrix with zero diagonal and entries $d_{ij}=|a_i-a_j|$. After ordering the $a_i$, one can perform row operations directly on $M$. Consecutive row differences become multiples of vectors with entries $(1,-1,-1,-1)$, $(1,1,-1,-1)$, and $(1,1,1,-1)$. Row reduction then immediately yields $x_2=x_3=0$ and $x_1=x_4$.
Another approach uses the fact that for ordered points on the real line,
$$|a_i-a_k|-|a_j-a_k|$$
is constant in $k$ whenever $i$ and $j$ are consecutive. This geometric property of distances on a line leads directly to the same three relations obtained in Lemma 1. The chosen proof is preferable because it keeps all computations explicit and requires only elementary algebra.