1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Need help with proof of sets of integers

  1. May 3, 2008 #1
    1.From the problem statement
    Let Z+ be the set of all positive integers; that is,
    Z+ = {1,2,3,...}
    Define Z+ x Z+ = {(a1, a2) : a1 is an element of Z+ and a2 is an element of Z+ }




    2. If S is contained in Z+ and |S| >=3, prove that there exist distinct x,y that are elements of S such that x+y is even.



    3. I need some help on where to start as I'm quite lost.
    I can see how this would be true. for example the set S = {1,2,3,4}
    The pairs (1,3) and (2,4) both satisfy the condition of x+y being even.


    the are extensions of this homework problem as well, but I'm having trouble with the first bit...
     
  2. jcsd
  3. May 3, 2008 #2

    exk

    User Avatar

    Try proof by contradiction:

    Assume that there are no elements x,y in S such that x+y is even and see where that leads you.

    You may want to note that since S has to contain 3 or more elements these can be all odd, all even or a combination. If they are all odd then adding two of them gives an even. if they are all even then adding any two gives an even and if it's a combination then once again combining two of them gives an even integer.
     
  4. May 4, 2008 #3
    how does this sound?
    there is a set S with three elements that are integers. Assume that any two of these elements are added together and always produce an odd value. (ie x1+x2 or x1+x3 or x2+x3 is always odd).

    assuming that all three elements of S have even values, take the sum of any two of these elements.
    k is even which makes k+2 even.
    k+k+2 = 2k+2. This value is even
    k+2 is even which makes k+2+2 even also.

    k+2+(k+2+2) = 2k+6. This value is even.

    assuming that all three elements of S have odd values, take the sum of any two of these elements.
    k is odd which makes k+2 odd.
    k+k+2 = 2k+2. This value is even
    k+2 is even which makes k+2+2 even also.

    k+2+(k+2+2) = 2k+6. This value is even.

    next assume that the set of S has elements some of which are even and some of which are odd.
    if two of the values are even, sum those two values. the result will be an even number.
    if two of the values are odd, sum those two values. the result will be an even number.

    Therefore, the original assumption that any two elements of S that are summed will produce an odd value is false.

    how is that?
    the third criteria seems weak.
     
  5. May 4, 2008 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    You didn't actually use your assumption that "any two of these elements are added together and always produce an odd value" so you might as well drop that: what you did was break the situation into cases: three members odd, three members even, 2 even and 1 odd, 1 even and 2 odd.
     
  6. May 4, 2008 #5
    ok
    so it's not really a proof by contradiction then.
    is it still sufficient though?
    I still feel like the wording could be better.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Need help with proof of sets of integers
Loading...