Question

Let n be an odd integer greater than 1 and let $c_1,c_2,\cdots ,c_n$ be integers. For each permutation $a=(a_1,a_2,\cdots ,a_n)$ of $(1,2,\cdots ,n)$ define $S\left(a\right)=\sum _{i=1}^n{c}_i{a}_i.$Prove that there exist permutations $a\ne b$ of $\{1,2,\cdots ,n\}$ such that n! is a divisor of S(a)-S(b).

• A. $\frac{1}{2}n!(n!-1)\equiv \frac{1}{2}(n+1)!\sum _{i=1}^n{c}_i(modn!).$ Because $n>1$ is odd, the right-hand side is congruent to 0 mod n!, while the lefthand side is not, a contradiction.
• B. $\frac{1}{2}n!(n!+1)\equiv \frac{1}{2}(n+1)!\sum _{i=1}^n{c}_0(modn!).$ Because $n>1$ is odd, the right-hand side is congruent to 0 mod n!, while the lefthand side is not, a contradiction.
• C. $\frac{1}{2}n!(n!-1)\equiv \frac{1}{2}(n-1)!\sum _{i=1}^n{c}_0(modn!).$ Because $n>1$ is odd, the right-hand side is congruent to 0 mod n!, while the lefthand side is not, a contradiction.
• D. None of the above

Answer 1

Answer: (A)

$\frac{1}{2}n!(n!-1)\equiv \frac{1}{2}(n+1)!\sum _{i=1}^n{c}_i(modn!).$ Because $n>1$ is odd, the right-hand side is congruent to 0 mod n!, while the lefthand side is not, a contradiction.

Denote by $\sum _{a}S\left(a\right)$ the sum of S(a) over all n! permutations of $\{1,2,\cdots ,n\}$. We compute $\sum _{a}S\left(a\right)$ (mod n!) in two ways. First, assuming that theconclusion is false, it follows that each S(a) has a differnt remainder mod n!, hencethese remainders are the numbers 0, 1, 2, ..., n!-1. It follows that $\sum _{a}S\left(a\right)\equiv \frac{1}{2}n!(n!-1)(modn!).$ On the other hand,$\sum _{a}S\left(a\right)=\sum _a\sum _{i=1}^n{c}_i{c}_i=\sum _{i=1}^n{c}_i\sum _a{a}_i.$ For each i, in $\sum _a{a}_i,$ each of the numbers 1, 2, ..., n, appears (n-1)! times, hence $\sum _a{a}_i=(n-1)!(1+2+\cdots +n)=\frac{1}{2}(n+1)!.$It follows that $\sum _{a}S\left(a\right)=\frac{1}{2}(n+1)!\sum _{i=1}^n{c}_i.$ We deduce that $\frac{1}{2}n!(n!-1)\equiv \frac{1}{2}(n+1)!\sum _{i=1}^n{c}_i(modn!).$ Because $n>1$ is odd, the right-hand side is congruent to 0 mod n!, while the lefthand side is not, a contradiction.