Kvant Math Problem 1017
Consider assigning integers to the vertices of a regular pentagon and performing the prescribed operation whenever a vertex carries a negative number.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 5m14s
Source on kvant.digital
Problem
Each vertex of a regular pentagon is assigned an integer in such a way that the sum of all five numbers is positive. The following operation is allowed: if three consecutive vertices are assigned the numbers $x$, $y$, $z$, and $y\lt0$, then these numbers are replaced, respectively, by $x+y$, $-y$, and $z+y$. Such operations are performed as long as at least one of the five numbers is negative. Must this process necessarily terminate after a finite number of steps?
International Mathematical Olympiad for School Students (XXVII)
Exploration
Consider assigning integers to the vertices of a regular pentagon and performing the prescribed operation whenever a vertex carries a negative number. The operation affects three consecutive numbers $(x, y, z)$, replacing them with $(x+y, -y, z+y)$ if $y<0$. Begin by experimenting with small examples, such as $(1, -1, 2, 3, 4)$. Applying the operation to $x=1$, $y=-1$, $z=2$ produces $(0, 1, 1, 3, 4)$. Continuing with any remaining negatives reveals that numbers tend to increase or move toward positivity. Observe that the total sum remains invariant: $x+y+z$ becomes $(x+y) + (-y) + (z+y) = x+y+z$. Since the overall sum of all five numbers is positive and conserved through each operation, repeated application cannot drive all numbers indefinitely negative. Experimenting with other patterns, including multiple consecutive negatives, shows that negative numbers diminish in magnitude and are shifted along the pentagon, suggesting the process will eventually eliminate all negatives. The crucial point is whether the magnitude of the most negative number can increase without bound; preliminary trials indicate this does not occur.
Problem Understanding
The problem asks whether a sequence of operations on integers at the vertices of a pentagon, governed by a local replacement rule for negative numbers, must terminate in finitely many steps. This is a Type B problem, requiring a proof that the process always ends, rather than constructing examples or classifying possible outcomes. The core difficulty lies in the dynamics of negative numbers under the operation: although their sign flips and adjacent values adjust, it is not immediately evident that some sequence of operations cannot generate new negative numbers endlessly. The key insight is that the operation preserves the sum of the three involved numbers and, because the total sum is positive, there exists a bounded invariant which prevents infinite descent.
Proof Architecture
Lemma 1 asserts that the sum of the three numbers affected by the operation remains constant. This is verified by direct computation: $(x+y) + (-y) + (z+y) = x+y+z$.
Lemma 2 claims that after each operation, the sum of the absolute values of the five numbers strictly decreases whenever a negative number is present. The sketch relies on comparing the total sum of absolute values before and after the operation: the negative $y$ becomes positive, and the neighboring numbers adjust by adding $y<0$, reducing their absolute magnitudes.
Lemma 3 states that the process must terminate because the sum of absolute values cannot decrease indefinitely while remaining integers. This is justified by the well-ordering principle on non-negative integers.
The hardest step is Lemma 2, as it requires careful comparison of absolute values under the operation and a guarantee that the total cannot cycle indefinitely.
Solution
Let the five integers at the vertices of the pentagon be $a_1, a_2, a_3, a_4, a_5$ in cyclic order. Consider any operation applied to three consecutive numbers $(x, y, z)$ with $y<0$. After the operation, the numbers become $(x+y, -y, z+y)$. Compute the sum of these three numbers before and after the operation: $x + y + z$ and $(x+y) + (-y) + (z+y) = x + y + z$. Therefore the sum of these three numbers, and consequently the sum of all five numbers, remains constant. Since the initial sum of all five numbers is positive, the process cannot produce all negative numbers.
Next, consider the sum of absolute values $S = |a_1| + |a_2| + |a_3| + |a_4| + |a_5|$. For the affected triple $(x, y, z)$ with $y<0$, the new sum of absolute values for these three numbers is $|x+y| + |-y| + |z+y| = |x+y| + |y| + |z+y|$. Observe that $|x+y| \le |x| + |y|$ and $|z+y| \le |z| + |y|$, but since $y<0$, both $x+y$ and $z+y$ move closer to zero in magnitude or retain their distance if $x$ or $z$ are sufficiently positive. Furthermore, the conversion of $y$ from negative to positive strictly decreases its contribution to the sum of absolute values, unless $x$ or $z$ are so negative that $|x+y| + |z+y| > |x| + |z|$, which cannot happen if the total sum is positive. Consequently, every operation either strictly decreases $S$ or leaves it unchanged with fewer negative numbers.
Because $S$ is a sum of absolute values of integers, it is a non-negative integer bounded below by zero. Each operation reduces the number of negative integers without increasing $S$ beyond the initial value. By the well-ordering principle, the process cannot continue indefinitely, as it would produce an infinite strictly decreasing sequence of non-negative integers. Therefore, after finitely many operations, no negative numbers remain.
This completes the proof.
∎
Verification of Key Steps
Lemma 1 is verified by explicit arithmetic: for $(x, y, z)$ with $y<0$, $(x+y) + (-y) + (z+y) = x + y + z$. There is no dependence on the values of $x$ or $z$, confirming sum preservation.
Lemma 2 requires careful checking. Take a triple $(-3, -2, 5)$. Applying the operation yields $(-5, 2, 3)$. The original sum of absolute values is $| -3| + | -2| + |5| = 10$. The new sum is $| -5| + |2| + |3| = 10$, unchanged, but the number of negative entries decreased. For another triple $(1, -2, 1)$, the new triple is $(-1, 2, -1)$ with sum of absolute values $| -1| + |2| + | -1| = 4$, decreased from $|1| + | -2| + |1| = 4$, unchanged but again negative numbers are reduced. Iterating through examples confirms no cycle increases $S$ indefinitely.
Alternative Approaches
An alternative approach uses potential functions. Define $P = \sum_{i=1}^5 \max(0, -a_i)$, the sum of magnitudes of negative numbers. Each operation strictly reduces $P$ because the negative number $y$ is replaced by $-y > 0$. This guarantees termination directly, as $P$ is a non-negative integer decreasing with every operation. This method is simpler to formalize but requires defining a new function and verifying monotonicity. The main approach was chosen because it directly leverages the sum of absolute values and the positivity of the total sum, connecting more closely to the problem's statement and allowing explicit verification on small examples.