Results 1 to 6 of 6

Math Help - Proof by Contradiction

  1. #1
    Member akhayoon's Avatar
    Joined
    Dec 2007
    From
    T.O
    Posts
    106

    Proof by Contradiction

    Let a1, a2....an be an arbitrary permutation of the numbers 1, 2,......, n,

    where n is an odd number. Prove by contradiction that the product

    (a1- 1)(a2 - 2)...(an - n) is even.

    Hint: Try to use the fact that the sum of an odd number of odd integers is odd.

    My Solution:

    I know that I have to prove that [(a1- 1)(a2 - 2)...(an - n) is odd] is false to able to prove this by contradiction.

    I don't understand how the hint can help me. but the only thing I know so far is that the product of odd numbers is odd (always). Not sure though how this can help me.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by akhayoon View Post
    Let a1, a2....an be an arbitrary permutation of the numbers 1, 2,......, n,

    where n is an odd number. Prove by contradiction that the product

    (a1- 1)(a2 - 2)...(an - n) is even.

    Hint: Try to use the fact that the sum of an odd number of odd integers is odd.

    My Solution:

    I know that I have to prove that [(a1- 1)(a2 - 2)...(an - n) is odd] is false to able to prove this by contradiction.

    I don't understand how the hint can help me. but the only thing I know so far is that the product of odd numbers is odd (always). Not sure though how this can help me.
    Proof by contradiction means you assume the premise and the opposite of the conclusion and then derive some contradiction.

    So, suppose (a1- 1)(a2 - 2)...(an - n) is odd. Then each of the factors must be odd. Continue.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member akhayoon's Avatar
    Joined
    Dec 2007
    From
    T.O
    Posts
    106
    Alright, so I'm thinking this now

    If each factor must be odd for the supposition that (a1- 1)(a2 - 2)...(an - n) is odd. We know for sure that this permutation will have even numbers, and therefore the supposition is false and we have some contradiction. Is that enough though?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by akhayoon View Post
    Alright, so I'm thinking this now

    If each factor must be odd for the supposition that (a1- 1)(a2 - 2)...(an - n) is odd. We know for sure that this permutation will have even numbers, and therefore the supposition is false and we have some contradiction. Is that enough though?
    Sorry but there is a huge gap in your reasoning. The permutation having even numbers does not by itself imply that one of the factors in (a1- 1)(a2 - 2)...(an - n) is even.

    Hint: We need to use the fact that n is odd.

    Hint 2: How many odd numbers are there in {1,2,...,n}? How many even numbers?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member akhayoon's Avatar
    Joined
    Dec 2007
    From
    T.O
    Posts
    106
    I can see from the second hint that in {1,2,...,n} there is always one more odd number than an even number. But I can't see the connection between the first hint and the result from the second hint to prove that [(a1- 1)(a2 - 2)...(an - n) is odd] is false.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by akhayoon View Post
    I can see from the second hint that in {1,2,...,n} there is always one more odd number than an even number. But I can't see the connection between the first hint and the result from the second hint to prove that [(a1- 1)(a2 - 2)...(an - n) is odd] is false.
    odd - odd = even
    odd - even = odd
    even - odd = odd
    even - even = even

    We must match each odd a_i with a unique even number from {1,2,...,n}. But there are not enough evens! (This is an example of the pidgeonhole principle.) So at least one odd number from {1,2,...,n} is assigned to an odd a_i. So that factor is even. Contradiction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Proof by contradiction
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: February 28th 2011, 11:06 AM
  2. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 11:07 PM
  3. Proof by contradiction
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 5th 2010, 05:17 PM
  4. Proof by contradiction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 11th 2009, 05:12 PM
  5. Proof By Contradiction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2007, 12:23 AM

Search Tags


/mathhelpforum @mathhelpforum