I write the integers 1-9999 (inclusive) on a huge chalkboard. Each number is written once.
During the night the board is visited by a series of naughty math elves (it’s a thing!)
Each elf approaches the board, selects two numbers at random, erases them, and replaces them with a new number that is the absolute difference of the two numbers erased.
This vandalism continues all night until there is just one number remaining.
I return to the board the next morning and find the single number of the board. The question is: Is this remaining number odd or even?
Is this remaining number odd or even?
Advertisement:
Solution
This problem can be solved, simply, with application of parity.
A number is either odd or even.
At the start of the night there are 9,999 numbers written on the board. Of these numbers, 5,000 are odd, and 4,999 are even.
When an elf selects a pair of numbers, there are three possible permutations. He can select two odd numbers, two even number, or one of each.
If he selects two odd numbers, the absolute difference between two odd numbers is always an even number. What has happened is that the quantity of odd numbers remaining has been reduced by two.
If he selects two even numbers, the absolute difference between a pair of even numbers is also even. The quantity of odd numbers remaining stays the same.
If he selects an odd and an even number, the absolute difference between this pair is odd. We lost one odd number, but gained a new one, so the quantity of odd numbers remaining stays the same.
From this you can see that either the quantity of odd numbers either stays the same, or reduces by two, with every act of defacement.
The quantity of odd numbers on the board started at 5,000, which is even, and has to remain even.
If we get down to a single number, it has to be an even number.