Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $n$ be an odd integer and let $f$ be an $n$-permutation of length $n$. 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.

share|improve this question

3 Answers 3

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

share|improve this answer
    
So all of i - f(i) are odd if you can fit (n+1)/2 odd i's into (n-1)/2 even f(i)'s and also fit (n+1)/2 odd f(i)'s into (n-1)/2 even i's? –  oks Feb 15 at 19:37
    
It is sufficient to consider the $(n+1)/2$ odd $i$s and the $(n-1)/2$ even $f(i)$s. Show that there must be an odd $i$ such that $f(i)$ is also odd. –  fkraiem Feb 15 at 19:43
    
@fkraiem I don't understand what this exactly means... –  user126032 Feb 15 at 19:57

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.