USA IMO 2003

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:

a) from a position with odd sum, move to a position with exactly one odd number; b) 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 $$A\begin{array}{cc}B& C\\ F& E\end{array}D$$ with odd sum. Then either $A+C+E$ or $B+D+F$ is odd; assume without loss of generality that $A+C+E$ is odd. If exactly one of $A,C$ and $E$ is odd, say $A$ is odd, we can make the sequence of moves $$1\begin{array}{cc}B& 0\\ F& 0\end{array}D\to 1\begin{array}{cc}1& 0\\ 1& 0\end{array}0\to 0\begin{array}{cc}1& 0\\ 1& 0\end{array}0\to 0\begin{array}{cc}1& 0\\ 0& 0\end{array}0(\mathrm{mod}2),$$ 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 $A,C,E$ are all odd, then the sequence of moves $$1\begin{array}{cc}B& 1\\ F& 1\end{array}D\to 1\begin{array}{cc}0& 1\\ 0& 1\end{array}0\to 1\begin{array}{cc}0& 0\\ 0& 0\end{array}0(\mathrm{mod}2),$$ 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 $$A\begin{array}{cc}B& C\\ F& E\end{array}D$$ with $A$ odd and all other numbers even. We want to reach a position with smaller maximum. Let $M$ be the maximum. There are two cases, depending on the parity of $M$.

In this case, $M$ is even, so one of $B,C,D,E,F$ is the maximum. In particular, $A<M$. We claim after making moves at $B,C,D,E$, and $F$ in that order, the sum is odd and the maximum is less than $M$. Indeed, the following \begin{array}{r@{\;}c@{\;}l@{\quad}l@{\quad}l} \begin{array}{cccc} & & \mathbf{1} & \\ & \mathbf{0} & \mathbf{0} & \\ \mathbf{1} & \mathbf{0} & \mathbf{0} & \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & \end{array} & \rightarrow & \begin{array}{c} \mathbf{1} \\ \mathbf{0} \\ \mathbf{1} \\ \mathbf{0} \\ \mathbf{0} \end{array} & \rightarrow & \begin{array}{cccc} \mathbf{1} & \mathbf{1} & \mathbf{0} & \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & \\ \mathbf{1} & \mathbf{0} & \mathbf{1} & \\ \mathbf{0} & \mathbf{1} & \mathbf{1} & \\ \mathbf{0} & \mathbf{0} & \mathbf{1} & \end{array} & \rightarrow \\ & & \begin{array}{cccc} \mathbf{1} & \mathbf{1} & \mathbf{1} & \\ \mathbf{0} & \mathbf{1} & \mathbf{1} & \\ \mathbf{1} & \mathbf{1} & \mathbf{1} & \\ \mathbf{0} & \mathbf{1} & \mathbf{1} & \\ \mathbf{1} & \mathbf{1} & \mathbf{1} & \end{array} & \rightarrow & \begin{array}{c} \mathbf{1} \\ \mathbf{0} \\ \mathbf{1} \\ \mathbf{0} \\ \mathbf{1} \end{array} & \pmod{2}. \end{array} shows how the numbers change in parity with each move. Call this new position $$A^{\prime }\begin{array}{c}{B}^{\prime }\\ F^{\prime }\end{array}{C}^{\prime }\begin{array}{c}{C}^{\prime }\\ E^{\prime }\end{array}{D}^{\prime }.$$ The sum is odd, since there are five odd numbers. The numbers $A^{\prime }$, $B^{\prime }$, $C^{\prime }$, $D^{\prime }$, $E^{\prime }$ are all less than $M$, since they are odd and $M$ is even, and the maximum can never increase. Also, $F^{\prime }=|A^{\prime }-E^{\prime }|\le \max \{A^{\prime },E^{\prime }\}<M$. So the maximum has been decreased.

In this case, $M$ is odd, so $M=A$ and the other numbers are all less than $M$. If $C>0$, then we make moves at $B$, $F$, $A$, and $F$, in that order. The sequence of positions is \begin{array}{r@{\;}c@{\;}l} \begin{array}{cccc} & & \mathbf{1} & \\ & \mathbf{0} & \mathbf{0} & \\ \mathbf{1} & \mathbf{0} & \mathbf{0} & \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & \end{array} & \rightarrow & \begin{array}{c} \mathbf{1} \\ \mathbf{0} \\ \mathbf{1} \\ \mathbf{0} \end{array} & \rightarrow \\ & & \begin{array}{cccc} \mathbf{1} & \mathbf{0} & \mathbf{0} & \\ \mathbf{0} & \mathbf{0} & \mathbf{1} & \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & \end{array} & \rightarrow \\ & & \begin{array}{cccc} \mathbf{0} & \mathbf{1} & \mathbf{0} & \\ \mathbf{1} & \mathbf{0} & \mathbf{0} & \\ \mathbf{0} & \mathbf{0} & \mathbf{0} & \end{array} & \pmod{2}. \end{array} Call this new position $$A^{\prime }\begin{array}{c}{B}^{\prime }\\ F^{\prime }\end{array}{C}^{\prime }\begin{array}{c}{C}^{\prime }\\ E^{\prime }\end{array}{D}^{\prime }.$$ The sum is odd, since there is exactly one odd number. As before, the only way the maximum could not decrease is if $B^{\prime }=A$; but this is impossible, since $B^{\prime }=|A-C|<A$ because $0<C<M=A$. Hence we have reached a position with odd sum and lower maximum. If $E>0$, then we apply a similar argument, interchanging $B$ with $F$ and $C$ with $E$. If $C=E=0$, then we can reach the all-zero position by the following sequence of moves: $$A\begin{array}{c}B\\ F\end{array}0D\to A\begin{array}{c}A\\ A\end{array}000\to 0\begin{array}{c}A\\ A\end{array}000\to 0\begin{array}{c}0\\ 0\end{array}0000.$$ (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.

---

Alternative solution.

(By Richard Stong) 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 $\{a,d\}$ with smallest possible $\max \{a,d\}$. 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 $a\ge d$ and consider an arc $(a,x,y,d)$ of the position a^{x \ y}^{* *}d Consider updating $x$ and $y$ alternately, starting with $x$. If $\max \{x,y\}>a$, then in at most two updates we reduce $\max \{x,y\}$. Thus, we can repeat this alternate updating process and we must eventually reach a point when $\max \{x,y\}\le a$, and hence this will be true from then on. Under this alternate updating process, the arc of the hexagon will eventually enter a unique cycle of length four modulo $2$ in at most one update. Indeed, we have $$\left(\begin{array}{cc}0& 0\\ \ast \ast & 0\end{array}\right)\to \left(\begin{array}{cc}1& 0\\ \ast \ast & 0\end{array}\right)\to \left(\begin{array}{cc}1& 1\\ \ast \ast & 0\end{array}\right)\to \left(\begin{array}{cc}0& 1\\ \ast \ast & 0\end{array}\right)\to \left(\begin{array}{cc}0& 0\\ \ast \ast & 0\end{array}\right)(\mathrm{mod}2)$$ and $$1^{\begin{array}{cc}0& 0\\ \ast & \ast \end{array}}0\to 1^{\begin{array}{cc}0& 0\\ \ast & \ast \end{array}}0(\mathrm{mod}2);1^{\begin{array}{cc}1& 0\\ \ast & \ast \end{array}}0\to 1^{\begin{array}{cc}1& 0\\ \ast & \ast \end{array}}0(\mathrm{mod}2)$$ $$1^{\begin{array}{cc}1& 1\\ \ast & \ast \end{array}}0\to 1^{\begin{array}{cc}1& 1\\ \ast & \ast \end{array}}0(\mathrm{mod}2);1^{\begin{array}{cc}0& 1\\ \ast & \ast \end{array}}0\to 1^{\begin{array}{cc}0& 1\\ \ast & \ast \end{array}}0(\mathrm{mod}2),$$ or $$0^{\begin{array}{cc}0& 1\\ \ast & \ast \end{array}}1\to 0^{\begin{array}{cc}1& 1\\ \ast & \ast \end{array}}1\to 0^{\begin{array}{cc}1& 0\\ \ast & \ast \end{array}}1\to 0^{\begin{array}{cc}0& 0\\ \ast & \ast \end{array}}1\to 0^{\begin{array}{cc}0& 1\\ \ast & \ast \end{array}}1(\mathrm{mod}2)$$ and $$0^{\begin{array}{cc}0& 0\\ \ast & \ast \end{array}}1\to 0^{\begin{array}{cc}0& 0\\ \ast & \ast \end{array}}1(\mathrm{mod}2);0^{\begin{array}{cc}0& 1\\ \ast & \ast \end{array}}1\to 0^{\begin{array}{cc}0& 1\\ \ast & \ast \end{array}}1(\mathrm{mod}2)$$ $$0^{\begin{array}{cc}1& 1\\ \ast & \ast \end{array}}1\to 0^{\begin{array}{cc}1& 0\\ \ast & \ast \end{array}}1(\mathrm{mod}2);0^{\begin{array}{cc}1& 0\\ \ast & \ast \end{array}}1\to 0^{\begin{array}{cc}1& 0\\ \ast & \ast \end{array}}1(\mathrm{mod}2).$$ Further note that each possible parity for $x$ and $y$ will occur equally often. Applying this alternate updating process to both arcs $(a,b,c,d)$ and $(a,e,f,d)$ of $$a^b{c}^{c}d,$$ we can make the other four entries be at most $a$ and control their parity. Thus we can create a position $$a^{x_1}{x}_2{d}^{x_5}{x}_4$$ with $x_i+x_{i+3}$ $(i=1,2)$ odd and $M_i=\max \{x_i,x_{i+3}\}\le a$. In fact, we can have $m=\min \{M_1,M_2\}<a$, as claimed, unless both arcs enter a cycle modulo $2$ where the values congruent to $a$ modulo $2$ are always exactly $a$. More precisely, because the sum of $x_i$ and $x_{i+3}$ is odd, one of them is not congruent to $a$ and so has its value strictly less than $a$. Thus both arcs must pass through the state $(a,a,a,d)$ (modulo $2$, this is either $(0,0,0,1)$ or $(1,1,1,0)$) in a cycle of length four. It is easy to check that for this to happen, $d=0$. Therefore, we can achieve the position $$a^a{a}^{a}0.$$ From this position, the sequence of moves $$a^a{a}^{a}0\to a^{\begin{array}{cc}0& a\\ 0& a\end{array}}0\to \begin{array}{cc}0& 0\\ 0& 0\end{array}0$$ completes the task.

---

Alternative solution.

(By Tiankai Liu) In the beginning, because $A+B+C+D+E+F$ is odd, either $A+C+E$ or $B+D+F$ is odd; assume without loss of generality it is the former. Perform the following steps repeatedly.

a. In this case we assume that $A,C,E$ are all nonzero. Suppose without loss of generality that $A\ge C\ge E$. Perform the sequence of moves $$A\stackrel{B}{\underset{F}{C}}D\to A\stackrel{(\mathbf{A}-\mathbf{C})}{\underset{(\mathbf{A}-\mathbf{E})}{C}}E\stackrel{(\mathbf{C}-\mathbf{E})}{\to }\mathbf{C}\stackrel{(A-C)}{(A-E)}\stackrel{C}{\underset{(\mathbf{A}-\mathbf{C})}{\to }}(C-E),$$ which decreases the sum of the numbers in positions $A,C,E$ while keeping that sum odd.

b. In this case we assume that exactly one among $A,C,E$ is zero. Assume without loss of generality that $A\ge C>E=0$. Then, because $A+C+E$ is odd, $A$ must be strictly greater than $C$. Therefore, $-A<A-2C<A$, and the sequence of moves $$A\stackrel{B}{\underset{F}{C}}0D\to A\stackrel{(\mathbf{A}-\mathbf{C})}{\underset{\mathbf{A}}{C}}0\stackrel{\mathbf{C}}{\to }\mathbf{C}\stackrel{(A-C)}{\underset{A}{\to }}(A-C)|\mathbf{A}-2\mathbf{C}|\mathbf{C},$$ decreases the sum of the numbers in positions $A,C,E$ while keeping that sum odd.

c. In this case we assume that exactly two among $A,C,E$ are zero. Assume without loss of generality that $A>C=E=0$. Then perform the sequence of moves $$A\stackrel{B}{\underset{F}{C}}0D\to A\stackrel{\mathbf{A}}{\underset{\mathbf{A}}{0}}0\stackrel{0}{\to }0\stackrel{A0}{\underset{A0}{0}}\stackrel{0}{\to }0\stackrel{0}{\underset{0}{0}}0.$$ By repeatedly applying step (a) as long as it applies, then doing the same for step (b) if necessary, and finally applying step (c) if necessary, $$\left(\begin{array}{ccc}0& 0& 0\\ 0& 0& 0\end{array}\right)$$ can eventually be achieved.