Results 1 to 2 of 2

Math Help - Proof by Contrapositive

  1. #1
    Junior Member utopiaNow's Avatar
    Joined
    Mar 2009
    Posts
    72
    Thanks
    1

    Proof by Contrapositive

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

    Here is my attempt at proof by Contrapositive:
    Let P: for each x \in S, the integer x and the sum of any 2 of the remaining 3 integers of S are of the same parity.

    Q: for each x \in S, the integer x and the sum of any 2 of the remaining 3 integers of S are of different parity.

    R: every pair of integers S are of the same parity.

    In logic symbols: P \vee Q \Rightarrow R

    Contrapositive:  \sim R \Rightarrow\ \sim P\ \wedge \sim Q

    So assume  \sim R : there exists a pair of integers of S of different parity. And show that \sim P\ \wedge \sim Q follows.

    \sim P: there exists x \in S, such that the integer x and the sum of any 2 of the remaining 3 integers of S are of the different parity.

    \sim Q: there exists x \in S, such that the integer x and the sum of any 2 of the remaining 3 integers of S are of the same parity.

    Without loss of generality, let a and b be the pair of integers with different parity and without loss of generality let a be even and b be odd. Then a = 2k for some k \in \mathbb{Z} and b = 2m + 1 for some m \in \mathbb{Z} .

    Case 1: Both remaining c and d are even. Then c = 2l for some l \in \mathbb{Z} and d = 2z for some z \in \mathbb{Z} .
    For b = 2m + 1, the sum of any 2 other integers will be of opposite parity because they are all even. So \sim P is satisfied.

    Here is where I'm stuck, to show \sim Q, I need an integer such that, the sum of any 2 of the remaining 3 integers have the same parity. But I can't have that because if I choose one of the even numbers, then I eventually have to select an odd number to be in the sum of the 2 of the remaining 3.

    Case 2: Both remaining c and d are odd.Then c = 2l + 1 for some l \in \mathbb{Z} and d = 2z + 1 for some z \in \mathbb{Z} .

    Same problem as case 1 except reversed. I can show \sim Q because for a = 2k , the 3 remaining are all odd numbers, so adding any 2 of those 3 will give an even number. So they have the same parity.

    But how do I show \sim P because if I choose an odd number, adding an odd number with an even number will still give an odd number, so the sum of those 2 will end up having the same parity again.

    Case 3: c and d are of different parity. Without loss of generality let c be even and d be odd. Then c = 2l for some l \in \mathbb{Z} and d = 2z + 1 for some z \in \mathbb{Z} .
    Case 3 I can't show either.

    I don't understand what I'm doing wrong. Any suggestions would be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello utopiaNow

    It's your proposition \sim Q that's wrong. You said:
    Q: for each x \in S, the integer x and the sum of any 2 of the remaining 3 integers of S are of different parity.
    and
    \sim Q: there exists x \in S, such that the integer x and the sum of any 2 of the remaining 3 integers of S are of the same parity.
    But you don't need the word
    any. You need simply show that \exists x, y, z \in S, such that x and y+z are the same parity.

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with a proof - Contrapositive or Contradiction?
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 24th 2010, 08:41 AM
  2. Proof by contrapositive
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 14th 2010, 03:45 PM
  3. contrapositive proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 5th 2010, 01:07 PM
  4. Simple Contrapositive Proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: December 19th 2009, 05:03 AM
  5. Contrapositive proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: September 27th 2009, 07:36 AM

Search Tags


/mathhelpforum @mathhelpforum