Parity of the Last Element in a Set Reduction Game
Start with the set $\{1, 2, 3, \ldots, 50\}$. At each step, pick any two elements, remove them both, and insert their absolute difference back into the set. Repeat until only one number remains.
Is that final number always even, always odd, or does it depend on the choices made? Prove your answer.
Hints
- Ask yourself: what quantity is preserved by the operation of replacing two numbers with their absolute difference? Think about parity.
- Check all three cases: both even, both odd, one of each. How does each case change the count of odd numbers in the set?
- The count of odd numbers in $\{1, \ldots, 50\}$ is $25$. Since each step changes that count by $0$ or $2$, its parity is fixed. What does that force the final element to be?
Worked Solution
How to Think About It: When you see a process that reduces a set one element at a time, the first question to ask is: what quantity is preserved? The absolute value operation is tricky -- it can map large numbers to small ones -- but it can't change parity. Even minus even is even; odd minus odd is even; even minus odd is odd. That means each step either leaves the count of odd numbers unchanged or decreases it by exactly 2. The parity of that count can never flip.
Key Insight: The parity of the count of odd numbers in the set is an invariant -- it is fixed from the very first step to the very last.
Proof:
Consider what happens when we replace $a$ and $b$ with $|a - b|$. There are three cases:
- Both even: $|a - b|$ is even. The count of odd numbers changes by $0$.
- Both odd: $|a - b|$ is even. We remove 2 odd numbers and add 1 even number. The count of odd numbers decreases by $2$.
- One even, one odd: $|a - b|$ is odd. We remove 1 odd number and add 1 odd number. The count of odd numbers changes by $0$.
In every case the count of odd numbers changes by $0$ or $-2$, so its parity (even or odd) is preserved throughout the entire process.
Initial state: In $\{1, 2, \ldots, 50\}$, the odd numbers are $1, 3, 5, \ldots, 49$. That is $25$ odd numbers -- an odd count.
Final state: One number remains. The count of odd numbers in a singleton set is either $0$ (even count, if the number is even) or $1$ (odd count, if the number is odd). Since the invariant says the count of odd numbers must stay odd, the final number must be odd.
Answer: The final remaining number is always odd, no matter what choices are made during the process.
Intuition
This problem is a classic example of finding a monovariant or invariant -- a quantity attached to the game state that cannot change in certain ways no matter what moves you make. Once you identify the right invariant (here, the parity of the count of odd numbers), the answer falls out immediately. The skill being tested is not algebraic manipulation but the ability to abstract away the specifics of the operation and ask: what is conserved?
This pattern appears constantly in quant interviews and in practice. In market microstructure, conserved quantities appear in zero-sum games between buyers and sellers. In options books, Greeks like delta aggregate across trades in ways that depend on invariants. In algorithm design, loop invariants are exactly this idea formalized. Any time you see a process that looks chaotic at the step level but must produce a deterministic global outcome, look for the invariant first.