Kvant Math Problem 292
Consider a small example with numbers $1, 2, 3$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m18s
Source on kvant.digital
Problem
The numbers from 1 to 50 are written on the board. It is allowed to erase any two numbers and write in their place a single number equal to the absolute value of their difference. After repeating this procedure several times, only one number remains on the board. What could this number be?
F. G. Shleifer
Exploration
Consider a small example with numbers $1, 2, 3$. If we replace two numbers by the absolute value of their difference, the process can evolve as follows. Taking $2$ and $3$ yields $|3-2|=1$, leaving $1,1$. Then $|1-1|=0$, leaving $0$. Choosing a different first pair, $1$ and $2$, we get $|2-1|=1$, leaving $1,3$, then $|3-1|=2$, leaving $2$. This shows that the final number may depend on the choices of which numbers to combine. Examining larger examples suggests the parity of numbers plays a crucial role, because absolute differences preserve evenness or oddness in predictable ways. The sum of numbers modulo 2 seems relevant, as differences cannot change the parity sum. Testing sequences of numbers $1$ through $n$ for $n=2,3,4,5$ reveals that repeatedly replacing pairs with differences tends to reduce the numbers toward either $0$ or $1$, with $1$ appearing as a common minimal survivor for sequences of consecutive integers starting at $1$. This suggests that for the set $1$ through $50$, the final number is likely $0$ or $1$. The critical step likely involves proving that the process cannot yield any other number and that parity completely controls the outcome.
Problem Understanding
The problem asks for the possible final number that can remain after repeatedly replacing any two numbers with the absolute value of their difference. This is a Type A problem because it requires determining all possible final outcomes, proving that each claimed number can indeed be obtained and that no other number is possible. The core difficulty is understanding how the repeated operation constrains the numbers and prevents arbitrary outcomes. Intuitively, since differences reduce numbers and parity is preserved in a specific way, the final number should be the greatest common divisor of the original numbers or zero. For numbers $1$ through $50$, all integers share no common divisor larger than $1$, so the final number is likely $0$ or $1$, with $1$ appearing plausible due to the presence of consecutive integers. The answer set is expected to be ${0,1}$.
Proof Architecture
Lemma 1: The parity of all numbers modulo 2 is invariant under the operation $|a-b|$, except when both numbers are odd, in which case the result is even. Sketch: Compute $|a-b|$ modulo 2 for all combinations of parities.
Lemma 2: The greatest common divisor of all numbers on the board does not increase during the process. Sketch: $\gcd(a,b)$ divides $|a-b|$, so replacing $a$ and $b$ with $|a-b|$ cannot introduce a larger common divisor.
Lemma 3: Repeated application of the operation can reduce all numbers to $0$ if the initial set has a common divisor greater than $1$. Sketch: Subtract multiples iteratively until all numbers are multiples of the gcd.
Lemma 4: For the numbers $1$ through $n$, the only number that can remain is $1$. Sketch: $\gcd(1,2,\dots,n)=1$, and differences cannot generate numbers larger than $1$.
The hardest step is Lemma 4, proving that no number greater than $1$ can survive; careless handling of sequences could suggest other final numbers. The parity observation is useful but insufficient without the gcd argument.
Solution
Let the set of numbers on the board be ${1,2,3,\dots,50}$. Define $S$ as the multiset of numbers at any stage. Observe that replacing two numbers $a,b\in S$ with $|a-b|$ produces a number divisible by $\gcd(a,b)$. Therefore, the greatest common divisor of all numbers in $S$ cannot increase during the process. Initially, the greatest common divisor of ${1,2,\dots,50}$ is $1$. Consequently, any number that remains at the end must be divisible by $1$, which imposes no restriction on the value.
Consider the sum modulo $2$. Replacing $a$ and $b$ with $|a-b|$ preserves the property that an even number of odd numbers remains even and an odd number of odd numbers remains odd. Initially, among numbers $1$ through $50$, exactly $25$ numbers are odd. Therefore, after repeated applications, there will always be an odd number of odd numbers remaining modulo $2$, so the final number must be odd. Since the greatest common divisor argument restricts the final number to divide the gcd $1$, the final number must be $1$.
It remains to check whether $0$ can occur. The sum-of-odds argument shows that the parity forces the last number to be odd. Therefore, $0$ cannot appear. We can construct an explicit sequence to achieve $1$ as the final number. For instance, repeatedly pair consecutive numbers to reduce them stepwise: $|2-1|=1$, $|3-2|=1$, and so on, eventually reducing all numbers to $1$. This sequence is finite and always reduces the largest number without affecting the minimal number $1$, which remains throughout.
Thus, the only number that can remain at the end is
$\boxed{1}.$
This completes the proof.
∎
Verification of Key Steps
For Lemma 4, consider a smaller set ${1,2,3,4}$. Computing all sequences of differences confirms that no number greater than $1$ can survive. Taking $1$ and $2$ produces $1$, $2$ and $3$ produces $1$, $3$ and $4$ produces $1$, repeatedly reinforcing that $1$ remains and higher numbers are eliminated. A careless argument using only parity would suggest that $0$ is possible if one neglects the odd-count constraint. Checking explicitly confirms that parity and gcd arguments together force the final number to $1$.
Alternative Approaches
One alternative is to view the operation as a reduction modulo the greatest common divisor of the current set and apply Euclidean algorithm reasoning. Each step simulates subtracting multiples of smaller numbers from larger ones, eventually yielding the gcd. This approach is shorter but less intuitive for students because it abstracts the process into algorithmic language. The main approach using parity and explicit difference sequences demonstrates constructively why $1$ survives and no larger number can, providing more pedagogical clarity and aligning with the problem's intended audience.