Problem:
At the vertices of a regular hexagon are written six nonnegative integers whose sum is 2003 . Bert is allowed to make moves of the following form: he may pick a vertex and replace the number written there by the absolute value of the difference between the numbers written at the two neighboring vertices. Prove that Bert can make a sequence of moves, after which the number 0 appears at all six vertices.
Note: Let
denote a position, where denote the numbers written on the vertices of the hexagon. We write
if we consider the numbers written modulo 2 .
Solution:
Define the sum and maximum of a position to be the sum and maximum of the six numbers at the vertices. We will show that from any position in which the sum is odd, it is possible to reach the all-zero position.
Our strategy alternates between two steps:
-
from a position with odd sum, move to a position with exactly one odd number;
-
from a position with exactly one odd number, move to a position with odd sum and strictly smaller maximum, or to the all-zero position.
Note that no move will ever increase the maximum, so this strategy is guaranteed to terminate, because each step of type (b) decreases the maximum by at least one, and it can only terminate at the all-zero position. It suffices to show how each step can be carried out.
First, consider a position
with odd sum. Then either or is odd; assume without loss of generality that is odd. If exactly one of and is odd, say is odd, we can make the sequence of moves
.jpg)
where a letter or number in boldface represents a move at that vertex, and moves that do not affect each other have been written as a single move for brevity. Hence we can reach a position with exactly one odd number. Similarly, if are all odd, then the sequence of moves
brings us to a position with exactly one odd number. Thus we have shown how to carry out step (a).
Now assume that we have a position
with odd and all other numbers even. We want to reach a position with smaller maximum. Let be the maximum. There are two cases, depending on the parity of .
- In this case, is even, so one of is the maximum. In particular, . We claim after making moves at , and in that order, the sum is odd and the maximum is less than . Indeed, the following sequence
.jpg)
shows how the numbers change in parity with each move. Call this new position . The sum is odd, since there are five odd numbers. The numbers , are all less than , since they are odd and is even, and the maximum can never increase. Also,
So the maximum has been decreased.
- In this case, is odd, so and the other numbers are all less than .
If , then we make moves at , and , in that order. The sequence of positions is
Call this new position . The sum is odd, since there is exactly one odd number. As before, the only way the maximum could not decrease is if ; but this is impossible, since because . Hence we have reached a position with odd sum and lower maximum.
If , then we apply a similar argument, interchanging with and with .
If , then we can reach the all-zero position by the following sequence of moves:
.jpg)
(Here 0 represents zero, not any even number.)
Hence we have shown how to carry out a step of type (b), proving the desired result. The problem statement follows since 2003 is odd.
Note: Observe that from positions of the form
it is impossible to reach the all-zero position, because a move at any vertex leaves the same value modulo 2. Dividing out the greatest common divisor of the six original numbers does not affect whether we can reach the all-zero position, so we may assume that the numbers in the original position are not all even. Then by a more complete analysis in step (a), one can show from any position not of the above form, it is possible to reach a position with exactly one odd number, and thus the all-zero position. This gives a complete characterization of positions from which it is possible to reach the all-zero position.
There are many ways to carry out the case analysis in this problem; the one used here is fairly economical. The important idea is the formulation of a strategy that decreases the maximum value while avoiding the "bad" positions described above.
Second Solution: We will show that if there is a pair of opposite vertices with odd sum (which of course is true if the sum of all the vertices is odd), then we can reduce to a position of all zeros.
Focus on such a pair with smallest possible . We will show we can always reduce this smallest maximum of a pair of opposite vertices with odd sum or reduce to the all-zero position. Because the smallest maximum takes nonnegative integer values, we must be able to achieve the all-zero position.
To see this assume without loss of generality that and consider an arc of the position
Consider updating and alternately, starting with . If , then in at most two updates we reduce . Thus, we can repeat this alternate updating process and we must eventually reach a point when , and hence this will be true from then on.
Under this alternate updating process, the arc of the hexagon will eventually enter an unique cycle of length four modulo 2 in at most one update. Indeed, we have
and
.jpg)
or
.jpg)
and
.jpg)
Further note that each possible parity for and will occur equally often.
Applying this alternate updating process to both arcs and of
we can make the other four entries be at most and control their parity. Thus we can create a position
with odd and . In fact, we can have , as claimed, unless both arcs enter a cycle modulo 2 where the values congruent to modulo 2 are always exactly . More precisely, because the sum of and is odd, one of them is not congruent to and so has its value strictly less than . Thus both arcs must pass through the state (modulo 2, this is either or ) in a cycle of length four. It is easy to check that for this to happen, . Therefore, we can achieve the position
From this position, the sequence of moves
completes the task.
The problems on this page are the property of the MAA's American Mathematics Competitions