Kvant Math Problem 826
The operation described on the board replaces one number with the sum of the other two numbers minus one.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m57s
Source on kvant.digital
Problem
Three numbers were written on the board. Then one of them was erased and replaced with the sum of the other two numbers, minus one. This operation was repeated several times, and as a result, the numbers 17, 1967, 1983 were obtained. Could the original numbers have been
- 2, 2, 2;
- 3, 3, 3?
A. A. Berzinsh
All-Union School Mathematics Olympiad (1983, 8th grade)
Exploration
The operation described on the board replaces one number with the sum of the other two numbers minus one. Denote the three numbers at any stage as $a$, $b$, $c$. Replacing $a$ gives the new triple $(b+c-1, b, c)$. Similarly, replacing $b$ or $c$ produces analogous triples. Observing the sum $S = a + b + c$, if we replace $a$, the new sum is $(b+c-1) + b + c = 2b + 2c - 1 = 2S - 2a - 1$. The sum changes linearly in the original numbers, suggesting a conserved quantity modulo 2 might be informative.
Trying small examples, starting from $(2,2,2)$, repeated operations give sums that grow quickly. For $(2,2,2)$, the sum $S=6$, and each operation produces $2_6 - 2_2 -1 = 12 -4 -1 =7$ sum? Actually, sum changes as $S_{\text{new}} = a+b+c + (b+c-1 - a) = S + (b+c-1 - a) = S + (S - a - a -1) = 2S - 2a -1$, confirming previous observation. Trying concrete steps, sums evolve: starting sum 6, replacing one 2: $S_{\text{new}} = 2_6 -2_2 -1 = 12-4-1=7$. This is odd, and iterating will continue producing integers. Eventually, can we reach 17, 1967, 1983? Their sum is $17 + 1967 + 1983 = 3967$. Check modulo patterns: starting with 6, sum parity is even, next sum 7 odd. Modulo 2, sequence alternates. The final sum 3967 is odd. Starting with 6 (even) yields final sum odd after odd number of steps. So parity alone does not forbid $(2,2,2)$.
For $(3,3,3)$, initial sum 9, odd. Replacing one number: $2_9 - 2_3 -1 = 18 -6 -1=11$, sum odd. Final sum 3967 odd, parity consistent. So parity test alone is insufficient. Another invariant is $S - 1$ modulo 2? Or perhaps modulo 3? Checking modulo 3: starting $(2,2,2)$, sum $6 \equiv 0 \pmod 3$. Operation: new sum $2S -2a -1 = 2*6 -4-1=7 \equiv 1 \pmod 3$. Next replacement changes sum further. Eventually, we must reach 3967 $\equiv 1 \pmod 3$, which seems possible. Better is to look for an invariant linear combination: define $f(a,b,c) = a+b+c -3$. Then replacing $a$, $a_{\text{new}} = b+c-1$, sum of new triple: $(b+c-1) + b + c = 2b + 2c -1 = 2(b+c) -1$. Express $S-3$ and track its evolution. Observing small examples, a more systematic approach is needed: perhaps working backward from final numbers, inverting the operation.
The operation $x \mapsto y + z -1$ is invertible: knowing the three numbers at any stage, the erased number can be recovered as $x = y + z -1 - x_{\text{new}}$? Better: the previous number replaced is $x_{\text{prev}} = y + z -1 - x_{\text{new}}$? Yes, rearranging, if $x_{\text{new}} = y + z -1$, then $x_{\text{old}} = y + z -1$? Wait, going backward, suppose final triple is $(17,1967,1983)$. Pick one number to invert: $x_{\text{prev}} = y + z -1 - x_{\text{current}}$? Test small cases: if numbers are $(2,2,3)$, replacing 3 gives new number $2+2-1=3$, works. So going backward, previous number is $y+z - x_{\text{current}} -1$? Yes, consistent. Therefore, working backward is feasible.
Problem Understanding
The problem asks whether it is possible to start from the uniform triples $(2,2,2)$ or $(3,3,3)$ and, after several iterations of the operation replacing one number with the sum of the other two minus one, reach the numbers $17$, $1967$, $1983$. This is a Type A problem, "Determine all X," since we must verify both that each proposed starting triple can or cannot lead to the final configuration. The core difficulty is identifying an invariant or a method to rule out or confirm that the sequence of operations can connect the proposed initial triples to the given final numbers. The likely decisive approach is to work backward from the final numbers using the inverse operation and examine if the starting triples are reachable. Intuitively, large numbers like 1967 and 1983 are unlikely to be reached from $(2,2,2)$ after a small number of operations.
Proof Architecture
Lemma 1. The sum of the three numbers evolves under the operation according to $S_{\text{new}} = 2(S - a) -1$, where $S$ is the sum of the current triple and $a$ is the number being replaced. This is a direct computation using the definition of the operation.
Lemma 2. The operation is invertible in the sense that, given a triple $(x,y,z)$ obtained from a previous triple $(x',y,z)$ by replacing $x'$, the previous value $x'$ satisfies $x' = y + z -1 - x$. This follows by algebraic rearrangement of the operation formula.
Lemma 3. The parity of the sum alternates with each operation if the replaced number has the same parity as the sum. This is verified by considering all parity combinations of the triple and the operation formula.
Lemma 4. Starting from the uniform triple $(2,2,2)$, the largest number achievable by any sequence of operations is strictly less than 1967. This is shown by iteratively bounding the growth of the largest number, observing that each operation increases a number by less than twice the maximum of the other two.
Lemma 5. Starting from $(3,3,3)$, the sequence of operations cannot reach the final triple $(17,1967,1983)$ because the differences between numbers are too large relative to the starting values. This is demonstrated by showing that the sum and parity constraints cannot produce such disparate numbers in any number of operations.
The hardest step is Lemma 4, which requires a careful bound on the growth of numbers; a naive assumption of exponential growth can fail if the increment is less than expected.
Solution
Let the final triple be $(17,1967,1983)$. Denote the numbers generically as $(x,y,z)$ and the sum as $S = x+y+z$. Replacing one number, say $x$, by $y+z-1$ gives the new sum $S_{\text{new}} = (y+z-1) + y + z = 2(y+z)-1 = 2(S-x)-1$, establishing Lemma 1.
To work backward, assume the last operation replaced the number $x$. Then the previous value $x_{\text{prev}}$ satisfies $x_{\text{prev}} = y+z-1 - x$, as verified by solving $x_{\text{new}} = y+z-1$ for $x_{\text{old}}$, establishing Lemma 2.
Consider the starting triple $(2,2,2)$. The sum is $6$, and each operation replaces a number $a$ with $b+c-1 = (S-a)-1$, so the new sum $S_{\text{new}} = S - a + (S-a-1) = 2(S-a) -1$. The sum increases by less than double the previous sum minus one, but starting from 6, the largest achievable number after one operation is $b+c-1 = 2+2-1=3$, which is less than the maximum of the final numbers. Any subsequent operations replace numbers by sums of the other two minus one, and the maximum number grows slower than linear in the largest number of the previous triple. More precisely, if $M$ is the largest number in a triple, replacing it produces at most $2M-1$, while $1967$ exceeds any number obtained from repeated doubling starting at $2$, even after ten operations. Concretely, after the first operation, the triple becomes $(3,2,2)$, $(2,3,2)$, or $(2,2,3)$, each with sum $7$, and the largest number $3$. Next operation increases largest number to at most $2_3-1=5$, then at most $2_5-1=9$, then $17$, then $31$, then $61$, then $121$, then $241$, then $481$, then $961$, then $1921$, then $3841$. Observing these bounds, it is possible to reach $1967$ in principle. We must examine parity. Starting from $(2,2,2)$, all numbers even, first operation: replace $2$ with $2+