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.

Quote:

---

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.

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?

Quote:

---

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?

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.

Quote:

---

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.