proof using pigeonhole principle

Question

I am struggling to come up with a proof to the following question(from cut-the-knot.org):

Prove that if n is odd,then for any permutation $p$ of the set $\{1,2,3...,n\}$ the product $$P(p) = (1-p(1))(2-p(2)) \cdots (n-p(n))$$ is necessarily even.

My best guess: Things that could potentially not result in an odd number

1. an even number from $p$ that could get subtracted from an odd number counterpart in $P(p)$
2. vice versa

Since there are more odd numbers in p than even numbers in $P$ , therewill always be an odd number left out which will team up with an odd number in $P$ to produce an even number which render the whole product even

Answer 1

Call $i - p(i)$ an "even part" if $i$ is even and an "odd part" if $i$ is odd.

If both $i$ and $p(i)$ are odd for some $i$, then $i - p(i)$ is even, which causes $P(p)$ to be even. Since $n$ is odd, there are fewer even parts in the product (pigeonholes) than odd numbers in the set $\{1, \dots, n\}$ (pigeons). It follows that $p(i)$ is odd for at least one odd part, from which the claim follows.

Answer 2

Since $$\sum_{k=1}^n(k-p(k))=0$$ is an even number and since $n$ is odd, there exists at least one of $1\le k\le n$, such that $k-p(k)$ is even, because otherwise, the sum must be an odd number. Therefore, the product $P(p)$ must be even.

Answer 3

If $n$ is odd $n=2k+1$ for some $k$. Then $\{1,2, ... n\}$ contains $k+1$ odd numbers and $k$ even numbers. Therefore, there are only $k$ even numbers for the odd numbers to get mapped to so one of the odd numbers, say $i$, must be mapped to an odd number $p(i)$. But an odd number minus an odd number is even so $(i-p(i))$ is even and therefore, the product is even.