Parity – 3 – Last Number Standing
The numbers 1 to 5 are written on a board. Then pairs of numbers are selected, erased, and replaced by their difference. This continues until there is a single number remaining. In the example below, that number is 1.
1 2 3 4 5 => 1 2 4 2
1 2 4 2 => 2 2 3
2 2 3 => 2 1
2 1 => 1
THE CHALLENGE
How small can that single number be? Can it be 0? Does your answer change if the numbers go from 1 to 6, or from 1 to 7?
1 2 3 4 5 => ?
EXPLORATION
For a given list of numbers, such as 1 to 5, which last numbers are possible? What is the
smallest and largest possible last number? When can 0 or the top number occur on the list of possibilities?
Notes
THE CHALLENGE
This is quite similar to the puzzle that asks which numbers are possible when we take the numbers from 1 to 5 and put addition or subtraction signs between each pair of numbers – for example, 1 + 2 + 3 – 4 + 5 or 1 + 2 – 3 + 4 + 5. The advantage of using this form of the puzzle is that no negative numbers will be involved.
A few easy notes to start with. All differences are nonnegative, so the final answer can never be less than 0. The numbers that get created from differences are either with the original numbers or from numbers derived from those numbers. So the maximum number that can be used with a difference is the largest number, which is 5. We want to know which of the numbers from 0 to 5 are possible final answers.
Look at this as an evens and odds problem. Start by counting the number of odd numbers. In the case of going from 1 to 5, that count is 3, which is itself an odd number. So, we have an odd number of odd numbers. Make a list of what happens when you take a difference: 1) If both numbers are even, the result is an even number and there is no change in the total number of odd numbers; 2) if one number is odd and the other is even, the result is an odd number and there is no change in the total number of odd numbers; and 3) if both numbers are odd numbers, then the result is an even number and the total number of odd numbers is reduced by two. In all cases, the total number of odd numbers either stays the same or is reduced by two.
Result: If we start with an odd number of odd numbers, we will end with an odd number (1) of them. If we start with an even number of odd numbers, then we will end with an even number (0) of them.
In the case of going from 1 to 5, we started with an odd number of odd numbers, so the final answer must be odd. The final answer must be 1,3 or 5. Some quick experimenting shows that they are all possible.
The analysis is exactly the same for the numbers from 1 to 6 because there are still three odd numbers.
For the range 1 to 7, there are now an even number of odd numbers, so there will be zero odd numbers at the end and the possible last numbers are 0, 2, 4, or 6 (which can all occur).
EXPLORATION
It is easy to see when 0 is possible. Start by pairing up consecutive numbers from the top and taking their differences. This gives a collection of 1’s. If there are an even number of 1’s, then you can get a 0, and if there are an odd number, you can get a 1. Not surprisingly, this is the same as finding out whether you started with an even or odd number of odd numbers. Take 1 to 7 as an example: (7 6) (5 4) (3 2) 1 => 1 1 1 1 => (1 1) (1 1) => 0 0 => 0.
You can do the same thing to see if the top number is possible. Pair up consecutive numbers starting at the top leaving out the top number. Take the differences of these pairs. You now have a list of 1’s together with the top number. Reduce the list of 1’s to either a single 0 or single 1. Take the difference of that with the top number!