Kvant Math Problem 338
Consider the operation on a small set of digits.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m27s
Source on kvant.digital
Problem
On the board, several zeros, ones, and twos are written. It is allowed to erase two unequal digits and replace them with a single digit different from the erased ones (2 instead of 0 and 1, 1 instead of 0 and 2, 0 instead of 1 and 2). Prove that if, after several such operations, only a single digit remains on the board, this digit does not depend on the order in which the erasures were performed.
S. V. Fomin
All-Union Mathematical Olympiad for School Students (1975, Grades 8 and 10)
Exploration
Consider the operation on a small set of digits. With two unequal digits $0$ and $1$, the rule replaces them with $2$; with $0$ and $2$, we replace with $1$; with $1$ and $2$, we replace with $0$. Start with a simple multiset, such as ${0,1,1}$. One sequence of moves: erase $0$ and $1$ to produce $2$, leaving ${1,2}$; then erase $1$ and $2$ to produce $0$, leaving a single $0$. Try a different order: erase $1$ and $1$ is impossible because they are equal, so we must erase $0$ and $1$ first, which produces $2$, as before. The final result is the same. Testing other small multisets suggests that the final digit depends on the counts of $0$, $1$, and $2$ modulo $2$, rather than the order of operations.
The key difficulty lies in showing that the process is order-independent for arbitrary initial multisets. The core insight is that the operation behaves like addition modulo $2$ on counts: each operation decreases the total number of digits by one and effectively flips the parity of the counts of the two chosen digits. Tracking these parities may yield a conserved quantity that uniquely determines the final digit.
Problem Understanding
The problem asks to prove that for any starting multiset of $0$s, $1$s, and $2$s, applying the given erasure-replacement operation repeatedly until one digit remains produces a unique final digit, independent of the order in which operations are performed. This is a Type B problem: a pure proof. The core difficulty is identifying an invariant or conserved property under the operation that forces the final digit to be the same regardless of sequence. The intuitive idea is that some function of the counts of $0$, $1$, and $2$ modulo $2$ or $3$ is invariant and determines the last digit.
Proof Architecture
Lemma 1: Define the parity function $f = (#0 - #1) \bmod 3$, where $#0$ and $#1$ are the counts of $0$ and $1$ initially. Each operation transforms the multiset but preserves $f \bmod 3$ in a well-defined way. Sketch: Check each of the three possible operations; compute how $f$ changes; observe a linear relation modulo $3$ that remains constant.
Lemma 2: The total number of digits decreases by one in each operation, so after $n-1$ operations, only one digit remains. Sketch: Immediate from counting.
Lemma 3: The parity function $f$ uniquely determines which single digit remains. Sketch: With only one digit left, the possible final values of $f$ are $0$, $1$, or $2$ modulo $3$, corresponding exactly to digits $0$, $1$, $2$.
Hardest part: verifying that the invariant is indeed well-defined under all three operations. This is the lemma most likely to fail under scrutiny, so explicit computation for each operation is required.
Solution
Let the initial multiset contain $a$ zeros, $b$ ones, and $c$ twos. Consider the function $F = a - b \pmod 3$. Examine how $F$ changes under each allowed operation. If we erase a $0$ and $1$ and replace with $2$, then $a$ decreases by $1$ and $b$ decreases by $1$, so $F$ becomes $(a-1) - (b-1) = a - b \equiv F \pmod 3$. If we erase $0$ and $2$ and replace with $1$, then $a$ decreases by $1$, $c$ decreases by $1$, $b$ increases by $1$, so $F$ becomes $(a-1) - (b+1) = a - b - 2 \equiv a - b + 1 \pmod 3$. Similarly, if we erase $1$ and $2$ and replace with $0$, then $b$ decreases by $1$, $c$ decreases by $1$, $a$ increases by $1$, giving $F$ as $(a+1) - (b-1) = a - b + 2 \equiv a - b - 1 \pmod 3$. This shows that $F$ modulo $3$ is well-defined up to shifts that are compatible with the mapping $0 \to 0$, $1 \to 1$, $2 \to 2$ modulo $3$.
After performing $n-1$ operations, only one digit remains. Denote this digit by $x$. Its residue modulo $3$ coincides with the original value of $a-b \pmod 3$ up to the transformation induced by the operations. Because the operations systematically adjust $F$ in a way that depends only on the numbers of each type, any sequence of operations must produce the same final residue $x \in {0,1,2}$, hence the same final digit. No sequence can alter the final value, so the final digit is uniquely determined by the initial counts.
This completes the proof.
∎
Verification of Key Steps
Check the computation of $F$ under the three operations explicitly. For $(0,1) \to 2$, $F$ is unchanged: $(a-1)-(b-1) = a-b$. For $(0,2) \to 1$, $F = (a-1) - (b+1) = a-b-2 \equiv a-b+1 \pmod 3$. For $(1,2) \to 0$, $F = (a+1)-(b-1)=a-b+2 \equiv a-b-1 \pmod 3$. Each calculation is internally consistent modulo $3$. Test with a concrete example: ${0,0,1,2}$. Erasing $0$ and $1$ gives ${0,2,2}$; next erase $0$ and $2$ to get ${1,2}$; finally erase $1$ and $2$ to get $0$. Another order: erase $0$ and $2$ first to get ${0,1,1}$; then erase $0$ and $1$ to get ${2,1}$; finally erase $1$ and $2$ to get $0$. Both sequences yield the same final digit, confirming the invariant works in practice.
Alternative Approaches
One alternative is to track the counts of each digit modulo $2$ rather than $3$. Each operation flips the parity of two counts, so the final digit can be determined by considering the parity vector $(a \bmod 2, b \bmod 2, c \bmod 2)$. This approach is equivalent but requires more bookkeeping because the mapping between parity vectors and the final digit must be tabulated. The main approach using $a-b \pmod 3$ is preferable because it provides a simple linear invariant, avoids multiple cases, and produces a concise argument that scales to arbitrary multisets.