Track / Stage 5 / 306 of 400 #906 of 1964

Problem 906

AIME late

Combinatorics Difficulty 5.7 Prove it

8. C2 (CAN) ${ }^{\mathrm{IMO4}}$ Let $n$ be an odd integer greater than 1 and let $c_{1}, c_{2}, \ldots$ , $c_{n}$ be integers. For each permutation $a=\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of $\{1,2, \ldots, n\}$ , define $S(a)=\sum_{i=1}^{n} c_{i} a_{i}$ . Prove that there exist permutations $a \neq b$ of $\{1,2, \ldots, n\}$ such that $n$ ! is a divisor of $S(a)-S(b)$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solutions — 2

Solution 1

8. Suppose to the contrary that all the $S(a)$ 's are different modulo $n$ !. Then the sum of $S(a)$ 's over all permutations a satisfies $\sum_{0} S(a) \equiv 0+1+\cdots+$ $(n!-1)=\frac{\langle n!-1) m!}{2} \equiv \frac{n!}{2}(\bmod n!)$ . On the other hand, the coefficient of $c_{i}$ in $\sum_{0} S(a)$ is equal to $(n-1)!(1+2+\cdots+n)=\frac{n+1}{2} n$ ! for all $i$ , from which we obtain
$\sum_{a} S(a) \equiv \frac{n+1}{2}\left(c_{1}+\cdots+c_{n}\right) n!\equiv 0(\bmod n!)$
for odd $n$ . This is a contradiction.

Solution 2

8. Suppose to the contrary that all the $S(a)$ 's are different modulo $n$ !. Then the sum of $S(a)$ 's over all permutations $a$ satisfies $\sum_{a} S(a) \equiv 0+1+\cdots+(n!-1)=\frac{(n!-1) n!}{2} \equiv \frac{n!}{2} \pmod{n!}$ . On the other hand, the coefficient of $c_{i}$ in $\sum_{a} S(a)$ is equal to $(n-1)!(1+2+\cdots+n)=\frac{n+1}{2} n!$ for all $i$ , from which we obtain
$\sum_{a} S(a) \equiv \frac{n+1}{2}\left(c_{1}+\cdots+c_{n}\right) n! \equiv 0 \pmod{n!}$
for odd $n$ . This is a contradiction.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.