Results 1 to 5 of 5
Like Tree2Thanks
  • 1 Post By johnsomeone
  • 1 Post By richard1234

Math Help - Numbers Proof

  1. #1
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    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.
    Last edited by johnsomeone; October 21st 2012 at 03:47 PM.
    Thanks from gfbrd
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    Re: Numbers Proof

    hey there thanks a lot for your help as always
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2012
    From
    AZ
    Posts
    616
    Thanks
    97

    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.
    Thanks from gfbrd
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2012
    From
    san francisco
    Posts
    92

    Re: Numbers Proof

    Thanks Richard for helping me out also
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof pentagonal numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2010, 07:58 AM
  2. Proof: All rational numbers are algebraic numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 5th 2010, 10:26 AM
  3. Proof with prime numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 25th 2009, 08:58 PM
  4. rational numbers proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 6th 2009, 12:33 AM
  5. Proof involving GCD of numbers
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: April 17th 2008, 03:35 AM

Search Tags


/mathhelpforum @mathhelpforum