1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @PedroTamaroff: I guess you mean even. For odd it won’t work. $\endgroup$ – bodo Feb 9 '14 at 8:24
  • $\begingroup$ Yes, sure. =) ${}$ $\endgroup$ – Pedro Tamaroff Feb 9 '14 at 8:25
  • $\begingroup$ $f$, should be written $f_n(i)$ and is the $i$th element of some permutation of $(1, 2, \dots n)$. $\endgroup$ – Karolis Juodelė Feb 9 '14 at 8:30
  • $\begingroup$ 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. $\endgroup$ – bodo Feb 9 '14 at 8:40
  • $\begingroup$ 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]$. $\endgroup$ – Marc van Leeuwen Feb 9 '14 at 8:45
3
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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