Prove a number is even using the Pigeonhole Principle

Question

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?

Answer 1

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 \} $

Answer 2

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.)

Answer 3

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)).$$