# Prove a number is even using the Pigeonhole Principle

Let n be an odd integer and let f be an [n]-permutation of length n, where [n] is the set of integers 1, 2, 3,...n

Show that the number

x = (1-f(1))*(2-f(2))*...*(n-f(n))


is even using the pigeonhole principle

In this case, I don't understand what this function f is. What is an [n]-permutation of length n? Take f(2) for example. Permutations of [2] would be 1,2 and 2,1. So the way the problem is worded, f(2) must equal 12 or 21. If that's correct, which one? Will this number x still be even regardless of which [n]-permutation f(n) is?

• @PedroTamaroff: I guess you mean even. For odd it won’t work.
– bodo
Feb 9 '14 at 8:24
• Yes, sure. =) ${}$ Feb 9 '14 at 8:25
• $f$, should be written $f_n(i)$ and is the $i$th element of some permutation of $(1, 2, \dots n)$. Feb 9 '14 at 8:30
• I think the confusion also stems from the fact that the information of being an permutation of the set $[n]$ and having length $n$ is redundant. I don’t think the term length is commonly used for a general permutation, but rather for cyclic ones.
– bodo
Feb 9 '14 at 8:40
• I think the confusion comes from the abuse of the term permutation in "permutations and combinations" where a permutation of $[n]$ could be shorter than $n$. What is meant her is simple a true permutation of $[n]$. Feb 9 '14 at 8:45

You can split the numbers $1, 2, .., n$ into two sets $A, B$ - $A$ containing all odd numbers and $B$, the even ones. Suppose that $i$ and $f(i)$ are not both in $A$ or $B$ for $i \in \{1, 2,... n \}$.

Suppose $n$ is odd. Then without loss of generality $|A| = |B| + 1$. Each member in $A$ must be mapped to a member in $|B|$. By the pigeonhole principle this is impossible so for at least one $j \in \{1, 2,... n \}$ , $j$ and $f(j)$ are both odd or both even.

$\implies 2 \ | \ (j - f(j))$ for some $j$.

$\implies 2 \ | \ (1-f(1))*(2-f(2))*...*(n-f(n)) \implies$ the product is even.

A permutation of length $n$ is a bijection from $\{1, 2,.., n \} \rightarrow \{1, 2,.., n \}$

• I think you can say that in at least one case both $j$ and $f(j)$ are odd. Feb 9 '14 at 8:55

There are $(n+1)/2$ odd numbers $i\in[n]$, and equally many numbers $i$ such that $f(i)$ is odd. Since that makes $n+1$ in all, the pigeonhole principle says that at least one $i$ is counted twice: both $i$ and $f(i)$ are odd. But then $i-f(i)$ is even, and so is the entire product.

Here is a proof without the pigeonhole principle, by contradiction. For the product to be odd, all $n$ factors $i-f(i)$ must be odd. But since $n$ is odd, that would make the sum of the factors odd as well. But that sum is $0$, isn't that odd? (Indeed it isn't.)

Observe that $$\sum_{i=1}^n (i - f(i)) = 0$$ Thus, the sum of an odd number of terms is $$0$$, so there exists at least one even term in this sum. Hence, $$2 \mid \prod_{i=1}^n (i - f(i)).$$