# 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

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

• Is the second term in that product supposed to be $2-p(2)$? – rschwieb May 10 '13 at 18:26
• @rschwieb apologies and yes it should be. – metric-space May 10 '13 at 18:27
• Your "best guess" seems like a perfectly fine proof to me! – fgp May 10 '13 at 18:35
• Playing devil's advocate, I want to pair each odd number with an even numbers and each even number with an odd, to keep the differences odd, thus the product odd. Can I do that with $\frac{n-1}{2}$ even numbers and $\frac{n+1}{2}$ odd numbers? – Joshua Shane Liberman May 10 '13 at 19:07
• what is $p(i)$? – The Substitute May 11 '13 at 20:42

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.
• the It follows part, can one actually make that jump? – metric-space May 10 '13 at 20:53
• @nerorevenge Since there are more pigeons than holes, we would normally conclude that some hole receives more than one pigeon. Since that is not an option here, we can instead say at least one of the pigeons (odd integers) is not assigned to any hole ("even parts" in $P(p)$). This pigeon has no choice but to occupy one of the odd parts. Translating back to the language of the problem, that means $p(i)$ is odd for at least one odd $i$. – Austin Mohr May 10 '13 at 23:23
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.
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.