3
$\begingroup$

Q) Let $3\leq n$ be an odd integer and let $a_1,a_2,\ldots,a_n$ be fixed integers. For each of the $n!$ permutations $\pi=(\pi_1,\pi_2,\ldots,\pi_n)$ of $(1,2,\ldots,n)$, define $$f(\pi) = a_1\pi_1 + a_2\pi_2 + \cdots + a_n\pi_n.$$

Prove that there exist two distinct permutations $a,b$ of $\left(1,2,...,n\right)$ such that $f(a)-f(b)$ is divisible by $n!$.

I was angling for a proof by contradiction:

If there are no distinct $a,b$ such that $f(a)-f(b)$ is divisible by $n!$ then no $a,b$ satisfy $f(a)=f(b)\; mod \; n!$. There are $n!$ permutations and values of any number $mod n!$ therefore $f(\pi) \; mod \; n!$ takes the values of 0 to $n!-1$ exactly once to ensure no such $a,b$ exist.

I think the next step I should take is to consider the sum of $f(\pi)$ but I am unsure how to compute this and if even this is the right method.

What is the best way to do this question, or proceed from my working (if correct)?

I was also wondering whether this result has any significance in an area of mathematics, these questions sometimes lead on as such.

$\endgroup$
2
  • $\begingroup$ what is BMO? brazilian math olympiad? $\endgroup$
    – Asinomás
    Commented Jan 12, 2015 at 0:08
  • $\begingroup$ British Mathematical Olympiad $\endgroup$ Commented Jan 12, 2015 at 0:11

2 Answers 2

3
$\begingroup$

You're exactly right. If you add $f(p)$ for all permutations then on the one hand you should get something that is not a multiple of $n!$ of $n!$ since $1+2+3\dots +n!=\frac{n!(n!+1)}{2}$ and $n!+1$ is odd. So you are short by a multiple of $2$. Hence what you have is congruent to $n!/2$

On the other hand each $a_i$ appears $(n-1)!$ times, hence you want $(n-1)!$ multiplied by the sum of the $a_i$. This is a contradiction because if $(n-1)!k\equiv (n!)/2$ then $2k\equiv n \bmod n!$ which is impossible since $2k$ is even and $n!$ too, while $n$ is odd.

This is a contradiction, the contradiction comes from assuming there is a permutation for each congruence class mod $n!$.

$\endgroup$
2
$\begingroup$

I don't think this particular result has much of a significance in mathematics, but the method of proof does.

Your idea about taking the sum is correct, and you should have tried to finish it. Here is a sketch of the whole solution:

We need to show that there exist two distinct permutations $c$ and $d$ of $\left(1,2,...,n\right)$ such that $f\left(c\right) - f\left(d\right)$ is divisible by $n!$. (I am calling them $c$ and $d$ rather than $a$ and $b$ since $a$ conflicts with the notation $a_1,a_2,...,a_n$.) In other words, we need to show that there exist two distinct permutations $c$ and $d$ of $\left(1,2,...,n\right)$ such that $f\left(c\right)\equiv f\left(d\right) \mod n!$. Assume the contrary. Then, the remainders of $f\left(\pi\right)$ modulo $n!$ for $\pi$ ranging over all $n!$ permutations of $\left(1,2,...,n\right)$ are pairwise distinct. As a consequence, these remainders must traverse all $n!$ possible remainders modulo $n!$ (because if $n!$ remainders modulo $n!$ are distinct, then they must traverse all $n!$ possible remainders modulo $n!$). The sum of these remainders thus must be $0 + 1 + ... + \left(n!-1\right)$. Therefore, $\sum\limits_\pi f\left(\pi\right) \equiv 0 + 1 + ... + \left(n!-1\right) \mod n!$, where the sum ranges over all permutations $\pi$ of $\left(1,2,...,n\right)$.

But $\sum\limits_\pi \underbrace{f\left(\pi\right)}_{=\sum\limits_{i=1}^n a_i \pi_i} = \sum\limits_\pi \sum\limits_{i=1}^n a_i \pi_i = \sum\limits_{i=1}^n a_i \sum\limits_\pi \pi_i$. For every $i \in \left\{ 1,2,...,n \right\}$, we have $\sum\limits_\pi \pi_i = \sum\limits_{j=1}^n \left(n-1\right)! j$ (because for every $j \in \left\{ 1,2,...,n\right\}$, there exist exactly $\left(n-1\right)!$ permutations $\pi$ of $\left\{ 1,2,...,n\right\}$ satisfying $\pi_i = j$). Hence, $\sum\limits_\pi f\left(\pi\right) = \sum\limits_{i=1}^n a_i \underbrace{\sum\limits_\pi \pi_i}_{= \sum\limits_{j=1}^n \left(n-1\right)! j = \left(n-1\right)! \sum\limits_{j=1}^n j} = \sum\limits_{i=1}^n a_i \left(n-1\right)! \underbrace{\sum\limits_{j=1}^n j}_{=\dfrac{n\left(n+1\right)}{2}}$ $ = \sum\limits_{i=1}^n a_i \left(n-1\right)! \dfrac{n\left(n+1\right)}{2} = \left(\sum\limits_{i=1}^n a_i\right) \underbrace{\left(n-1\right)! n}_{= n!} \dfrac{n+1}{2} = \left(\sum\limits_{i=1}^n a_i\right) n! \dfrac{n+1}{2}$. This is divisible by $n!$ (since $\dfrac{n+1}{2}$ is an integer (since $n$ is odd)). In other words, $\sum\limits_\pi f\left(\pi\right) \equiv 0 \mod n!$. Compared with $\sum\limits_\pi f\left(\pi\right) \equiv 0 + 1 + ... + \left(n!-1\right) \mod n!$, this yields $0 \equiv 0 + 1 + ... + \left(n!-1\right) = \dfrac{\left(n!-1\right) n!}{2} \mod n!$. In other words, $n! \mid \dfrac{\left(n!-1\right) n!}{2}$, so that $2n! \mid \left(n!-1\right) n!$ and thus $2 \mid n!-1$. But this contradicts the fact that $n!$ is even (since $n \geq 2$).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .