# BMO preparatory question

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.

• what is BMO? brazilian math olympiad? Commented Jan 12, 2015 at 0:08
• British Mathematical Olympiad Commented Jan 12, 2015 at 0:11

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

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