proof using pigeonhole principle 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

*

*an even number from $p$ that could  get subtracted from an odd number counterpart in $P(p)$

*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 
 A: 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.
A: 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.
A: 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.
