$n$ be an odd integer and $f$ be a permutation of $\{1,2,\dots,n\}$.Show that the number $x = (1-f(1))\cdot(2-f(2))\cdot...(n-f(n))$ is even.

Question

Let $n$ be an odd integer and let $f$ be a permutation of $\left\{1,2,\ldots,n\right\}$. Show that the number

\begin{equation}x = (1-f(1))\cdot(2-f(2))\cdot...(n-f(n))\end{equation} is even.

I don't understand how the Pigeonhole principle can apply to this problem. Any help is appreciated.

Answer 1

Hint: $x$ is even if at least one of the numbers $i-f(i)$ is even.

Answer 2

As @5xum said, only one $i-f(i)$ needs to be even.

And as @fkraiem said, notice that there will be $(n+1)/2$ odd values (for both $i$ and the permuted sequence $f(i)$) and $(n-1)/2$ even values for (for both $i$ and the permuted sequence $f(i)$).

Now consider the outcome for a given term $i-f(i)$:

$i$ is odd and $f(i)$ is odd --> $i-f(i)$ is even
$i$ is odd and $f(i)$ is even --> $i-f(i)$ is odd
$i$ is even and $f(i)$ is odd --> $i-f(i)$ is odd
$i$ is even and $f(i)$ is even --> $i-f(i)$ is even

So for $(1-f(1))\cdot (2-f(2) \cdots (n-f(n))$ to be odd, every term in the product must be odd, and thus every term must represent a "mismatch" between $i$ and $f(i)$, where exactly one of those is odd and the other is even.

The pigeonhole principle can be used by saying that since there is exactly one more odd number than even number in the sequence $1, 2, \ldots n$, assume that the first $n-1$ terms (in any order) of the product are odd, i.e., for each of those terms pair exactly one even (either $i$ or $f(i)$) with one odd ($f(i)$ or $i$, respectively); however, you will simply run out of even numbers to pair with the odd numbers, because there is exactly one more odd number than there are even numbers. So if you assume the first $n-1$ terms (in any order) of the product are all odd, then the remaining term must be even, because it cannot pair an odd with an even.

In summary, for an integer product to be odd, all of its terms must be odd. By trying to make every term in the product odd, you simply run out of even numbers to pair with odd numbers (a necessity to make an odd term in the product), and thus can "force" an even term. This notion of running out of options and therefore forcing a particular outcome is similar to the pigeonhole principle.

Also, observe that it would not be possible to prove if $n$ was even (contrary to the assumptions in your question). If $n$ was even, then it would be possible (although unlikely) to pair every odd number with an even number, producing all odd terms in the product.

Happy mathing, I hope this helps.

Answer 3

Here's another approach that doesn't use Pigeonhole Principle

$x$ is odd if and only if all the terms are odd. If all the terms are odd, and there are an odd number of them, their sum cannot be 0 which is even.