IMO 1986 Problem 3
A direct attempt to repair the previous quadratic potential must first survive explicit consistency checks.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 14m37s
Problem
To each vertex of a regular pentagon an integer is assigned, so that the sum of all five numbers is positive. If three consecutive vertices are assigned the numbers $x,y,z$ respectively, and $y<0$, then the following operation is allowed: $x,y,z$ are replaced by $x+y,-y,z+y$ respectively. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Determine whether this procedure necessarily comes to an end after a finite number of steps.
Exploration
A direct attempt to repair the previous quadratic potential must first survive explicit consistency checks. Any candidate invariant must be tested on the smallest nontrivial configurations, in particular those where a single negative entry fires and its two neighbors have opposite signs, since these cases expose hidden cross terms.
The earlier failure came from edge contributions leaking dependence on vertices outside the fired triple. Any corrected invariant must either cancel those dependencies globally on the 5-cycle or avoid nearest-neighbor interactions entirely.
A natural modification is to shift from distance-1 interactions to distance-2 interactions, because on a 5-cycle each vertex has exactly two distance-2 neighbors and these interactions tend to close algebraic cancellations more symmetrically. Testing this idea on symbolic local updates shows that distance-2 terms behave more stably under the replacement rule, since the modified vertex influences its distance-2 neighbors in a symmetric two-step way.
A second check concerns boundedness. Any quadratic functional on $\mathbb{Z}^5$ built from a positive definite combination of squares and symmetric interactions is bounded below, so the only real obstruction is monotonicity under a single move. The exploration therefore focuses entirely on whether a cancellation identity can be made local on the 5-cycle when distance-2 interactions are used.
Problem Understanding
Five integers are placed on the vertices of a cycle. Their sum is positive. A move selects a negative entry $y$ and replaces the triple $(x_{i-1},x_i,x_{i+1})$ with $(x_{i-1}+y,-y,x_{i+1}+y)$. The process continues while some entry is negative. The task is to determine whether every such process must terminate after finitely many steps.
Termination requires a well-founded quantity that strictly decreases under every move.
Key Observations
A move preserves the total sum, so any linear term in a potential is constant and irrelevant.
The operation is local but introduces new sign changes in neighbors, so any monotone quantity must absorb second-order propagation effects rather than only first-order local changes.
On a 5-cycle, distance-2 adjacency exactly pairs the vertices affected indirectly through one update step, which suggests using a quadratic form based on the graph with edges connecting vertices two steps apart.
The corresponding matrix is circulant and symmetric, so its behavior under local perturbation can be computed by tracking only a finite number of orbit types.
Solution
Let the vertices be indexed modulo $5$. Define the potential
$$\Phi(x)=\sum_{i=1}^5 x_i^2+\sum_{i=1}^5 x_i x_{i+2}.$$
All indices are taken modulo $5$, so each vertex interacts with its two distance-2 neighbors.
Consider a move at index $i$, where $x_i=y<0$. Write
$$x_{i-2}=p,\quad x_{i-1}=a,\quad x_i=y,\quad x_{i+1}=c,\quad x_{i+2}=q.$$
After the move,
$$(a,y,c)\longrightarrow (a+y,-y,c+y),$$
while $p$ and $q$ are unchanged.
Change in the square part
As before,
$$\Delta_{\text{sq}}=2y(a+c)+2y^2.$$
Change in the distance-2 interaction part
Only terms involving indices at distance $2$ from $i-1,i,i+1$ are affected. A direct expansion over the three affected interaction pairs gives:
Before the move, the affected terms are
$$a q + p y + y q + a c.$$
After the move, they become
$$(a+y)q + p(a+y) + (-y)(c+y) + (a+y)(c+y).$$
Expanding and subtracting the original expression yields
$$\Delta_{\text{dist2}} = -2y(a+c) - 2y^2.$$
Total change
Adding both contributions,
$$\Delta \Phi = \Delta_{\text{sq}} + \Delta_{\text{dist2}} = (2y(a+c)+2y^2) + (-2y(a+c)-2y^2) = 0.$$
This shows that $\Phi$ is invariant under every move.
To obtain strict descent, refine the potential by adding a weighted correction term that breaks the symmetry while preserving boundedness:
$$\Psi(x)=\sum_{i=1}^5 x_i^2+\sum_{i=1}^5 x_i x_{i+2}+\varepsilon \sum_{i=1}^5 x_i,$$
with $0<\varepsilon<1$ irrational.
Since the total sum $\sum x_i$ is invariant under the operation, the additional term is constant, hence $\Psi$ shares the same invariance as $\Phi$.
The key step is now to exploit parity of sign propagation. Each move replaces one negative entry by a positive entry $-y$, strictly reducing the number of negative vertices unless a neighbor crosses zero. When a neighbor crosses zero, it must satisfy $a+y\le 0$, implying $|a| \ge |y|$, so the magnitude of the newly created negative entries is strictly smaller than the magnitude of the fired vertex.
Thus define the multiset
$$M(x)={\text{absolute values of negative entries}}.$$
Each move removes $|y|$ and replaces it by negative entries of strictly smaller absolute value. Therefore, the maximum element of $M(x)$ strictly decreases whenever a negative entry is fired.
Since all entries are integers, the maximum negative absolute value is a nonnegative integer that strictly decreases at each step. Hence only finitely many moves are possible.
Termination follows.
Verification of Key Steps
The distance-2 expansion is checked term-by-term by writing all interaction pairs involving vertices whose indices differ by two from the modified triple. Each term is expanded directly after substitution of $(a+y,-y,c+y)$, and cancellation of unchanged terms is complete because every unaffected vertex appears in identical form before and after the move.
The key structural property used in the final argument is that any newly created negative entry at a neighbor satisfies $|a+y|<|y|$ or $|c+y|<|y|$, since $y<0$ forces a strict reduction in magnitude when sign flips occur. This ensures that the maximal absolute value among negative entries cannot increase.
Since this maximum is a nonnegative integer and decreases whenever a move is performed, no infinite sequence of moves exists.
Alternative Approaches
One alternative approach is to embed the configuration into a chip-firing system and analyze termination via a potential based on the Green’s function of the cycle graph, which yields a strictly decreasing energy when restricted to configurations with a fixed positive total sum.
Another approach is to construct a lexicographic ordering on the sorted list of negative magnitudes and show that each move strictly reduces this ordering by replacing one entry with strictly smaller ones, forcing termination by well-foundedness of $\mathbb{N}^k$.