Numbers Proof

• Oct 21st 2012, 01:52 PM
gfbrd
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.
• Oct 21st 2012, 03:43 PM
johnsomeone
Re: Numbers Proof
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.
• Oct 21st 2012, 06:00 PM
gfbrd
Re: Numbers Proof
hey there thanks a lot for your help as always :)
• Oct 21st 2012, 10:07 PM
richard1234
Re: Numbers Proof
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.
• Oct 22nd 2012, 12:45 PM
gfbrd
Re: Numbers Proof
Thanks Richard for helping me out also :)