Thread: Numbers Proof

Hey there I need some help again. Hope you guys can help me out.


The numbers 1-50 are written on the blackboard. Then two numbers
a and b are chosen and replaced by the single number |a-b|: After 49 operations
a single number is left. Prove that it is is odd.

So far what I got is that since there is an odd number of odd numbers(25) we can say that no matter what combination of numbers you use, it will always come out odd because of this.

Dont think this will work as a proof, was hoping if someone can guide me through this problem better thanks.

Actually, that's absolutely the right idea.
Let f(n) = the number of odd numbers in your list when you have n numbers.
Have f(50) = 25.
Let g(n) = 1 if f(n) is odd, and g(n) = 0 if f(n) is even.
Have g(50) = 1.

Now, when there are k numbers:
Case: you pick two odds, remove them, subtract them, take absolute value, then reinsert the (even!) result:
Then f(k-1) = f(k) - 2 + 0 = f(k) - 2, so g(k-1) = g(k).
Case: you pick two evens, remove them, subtract them, take absolute value, then reinsert the (even!) result:
Then f(k-1) = f(k) - 0 + 0 = f(k-1), so g(k-1) = g(k).
Case: you pick an even and an odd, remove them, subtract them, take absolute value, then reinsert the (odd!) result:
Then f(k-1) = f(k) - 1 + 1 = f(k-1), so g(k-1) = g(k).
Now matter which two values you choose, g(k-1) = g(k).
(In math lingo, you might phrase this as "The parity of the number of odds on the list is invariant under this process.")
Thus g(1) = g(2) = g(3) = ... = g(49) = g(50) = 1.
Thus g(1) = 1.
Thus f(1) is odd.
Thus f(1), which the number of odd numbers in your list when you have only one number, is odd.
But on a list with only one number, that's only possible if that one number is odd, so that there's one (1 is odd) number that's odd on that list.
Thus, when your process terminates with 1 number remaining, that number must be odd.

hey there thanks a lot for your help as always

Use an invariant: If you choose two numbers a and b (assume a > b) and replace them with a-b, the parity of the sum of all the integers on the blackboard never changes. That is, the sum of all the integers on the blackboard will always be even or always be odd. This is because a+b is congruent to a-b mod 2.

Since the original sum is odd (1+2+...+50 = 50*51/2 = 25*51), the last number remaining will also be odd.

Thanks Richard for helping me out also