Al writes the numbers 1, 2, …, 2n on a blackboard, where n is an odd positive integer. He then picks any two numbers a and b, erases them, and writes instead |a – b|. He keeps doing this until one number remains. Prove that this number is odd.
|
SelectClick for Answer |
Denote by S the sum of all the numbers that remain on the blackboard. At the start this sum is S = 1 + 2 + … + 2n = n(2n + 1), which is odd. Each step reduces S by 2 min(a, b), which is an even number. Thus the parity of S never changes. Since it started odd, it will end odd.
From Arthur Engel’s Problem-Solving Strategies, 2003.
09/01/2024 UPDATE: Readers Seth Cohen and Robert Filman point out a simpler solution. In Seth’s words:
Call the number of odd numbers on the board n. At the start, n is odd.
- If a and b are even, so is a–b, so you don’t lose or gain any odd numbers, so n is still odd.
- If a and b are odd, a–b is even. So you lose two odd numbers and gain none, and n remains odd.
- If a and b are one odd and one even, a–b is odd. You lose an odd number and gain an odd number. Thus, n stays odd.
No matter what you do, n is always odd, so once you’re down to one number, it’ll be odd.
Thanks to both.
|
