Pigeonhole Principle Proof and Existence

Question

So, I’m going through a textbook on combinatorics, and I came across this exercise question.

Let $n$ be odd, and suppose $(x_1, x_2, \dots, x_n)$ is a permutation of $[n].$ Prove that the product of $(x_1-1)(x_2-2) \cdots (x_n-n)$ is even.

So far, I have this: in order for the product to be even, we need to have an even number of odd integers $x_i$ and an odd number of even integers $x_j-j$. But neither do I think this helps nor do I see a way of tying it up to arrive at a proof.

Furthermore, this section of the chapter involves the Pigeonhole Principle, so I’m sure the author wants us to incorporate that into each proof, but I can’t seem to do this either.

Any help would be much appreciated. :) Thanks in advance.

Answer 1

Your pigeons are the odd $x_i$, your holes are the even $i$.

Answer 2

Think the other way. What would have to happen for the product to be odd? Because the product can only be either odd or even.

For it to be odd, you need to be able to match even numbers for odd $i$ and odd numbers for even $i$, for every $i$ in your product. Otherwise, you will have at least one term even and that will get you an even product. But if $n$ is odd, you will always have more odd numbers than even numbers. More specifically $(n-1)/2$ even numbers and $(n+1)/2$ odd numbers. Thus there is NO way to put all odd numbers with even $i$. Hence the product has to be even.

The problem to me has more to do with parity than PHP.

Answer 3

This problem has a proof that does not require a pigeonhole principle. Notice that $$\sum_{i=1}^{n}{x_i}=\sum_{i=1}^{n}{i},$$ since $(x_1,\dots,x_n)$ is just a permutation of $(1,\dots,n)$. Therefore, $$\sum_{i=1}^{n}{(x_i-i)}=\sum_{i=1}^{n}{x_i}-\sum_{i=1}^{n}{i}=0,$$ which is even. Since $n$ is odd, we have that a sum of an odd number of integer summands $x_i-i$ ($i=1,\dots,n$) is even, so at least one of them is even (since if they're all odd, then the sum is also odd). Thus, the product $\prod_{i=1}^{n}{(x_i-i)}$ is even.