Results 1 to 5 of 5

Math Help - Proof about parity of a set of four integers

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    43

    Proof about parity of a set of four integers

    Statement to prove:

    Let S={a,b,c,d} be a set of four distinct integers. Prove that if either (1) for each xES, the integer x and the sum of any two of the remaining three integers of S are of the same parity or (2) for each xES, the integer x and the sum of any two of the remaining three integers of S are of opposite parity, then every pair of integers of S are of the same parity.


    I have two proofs of this statement and I want to make sure they are correct. In the first one I assume that some pair of integers of S are of different parity, and in four different cases show that neither condition (1) or condition (2) is satisfied. So proof by contrapositive.

    In the second I assume that every pair of integers in S are of opposite parity. Since this is always false (right?) the contrapositive is a true statement and I'm done. So a vacuous proof of the contrapositive. I'm unsure of this one because so far I haven't seen a two proof methods combined.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by zg12 View Post
    Statement to prove:

    Let S={a,b,c,d} be a set of four distinct integers. Prove that if either (1) for each xES, the integer x and the sum of any two of the remaining three integers of S are of the same parity or (2) for each xES, the integer x and the sum of any two of the remaining three integers of S are of opposite parity, then every pair of integers of S are of the same parity.


    The last words above are a little odd for me (pun intended): to say, in this case, that "every pair of integers of

    S are of the same parity" is exactly the same as saying that all the integers in S have

    the same parity...unless I missed something.

    Tonio



    I have two proofs of this statement and I want to make sure they are correct. In the first one I assume that some pair of integers of S are of different parity, and in four different cases show that neither condition (1) or condition (2) is satisfied. So proof by contrapositive.

    In the second I assume that every pair of integers in S are of opposite parity. Since this is always false (right?) the contrapositive is a true statement and I'm done. So a vacuous proof of the contrapositive. I'm unsure of this one because so far I haven't seen a two proof methods combined.
    .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2010
    Posts
    43
    That's how I read it too. And I found the question and answer elsewhere and my first proof is indeed correct. And if we're reading it correctly I think that the second proof is ok too, since assuming some pair of integers are of opposite parity and all pairs of integers are of opposite parity are both negations of the statement "all pairs of integers are of the same parity."
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,530
    Thanks
    773
    some pair of integers are of opposite parity and all pairs of integers are of opposite parity are both negations of the statement "all pairs of integers are of the same parity."
    No way.

    Let p(x) denote the parity of x. "All pairs of integers are of the same parity" is \forall x,y\in S.\,x\ne y\to p(x)=p(y). Its negation is \exists x,y\in S.\,x\ne y\land p(x)\ne p(y), i.e., "some pair of integers are of opposite parity". The statement "all pairs of integers are of opposite parity" is \forall x,y\in S.\,x\ne y\to p(x)\ne p(y). It implies the previous statement, but then falsehood implies everything.

    The following should have given you a warning bell. The conclusion of the claim you need to prove — "all the integers in S have the same parity" — is not true for all S, so it essentially uses the premise (that (1) or (2) holds). However, in your second proof you ignore this premise.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Mar 2010
    Posts
    43
    Quite right emakarow, thank you.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Parity proof with binomial coefficients
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 24th 2011, 12:57 PM
  2. Proof on Integers, sa+tb=n
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 9th 2010, 07:33 AM
  3. integers proof
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 7th 2010, 05:46 PM
  4. Proof of integers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 10th 2009, 02:33 PM
  5. Integers and proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 18th 2009, 08:39 AM

/mathhelpforum @mathhelpforum