# Math Help - Proof by Contradiction

1. ## 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.

2. Originally Posted by akhayoon
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.

3. 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?

4. Originally Posted by akhayoon
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?

5. 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.

6. Originally Posted by akhayoon
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.