Problem=

Let $n_1, n_2, \dots , n_m$ be integers where $m>1$ is odd. Let $x = (x_1, \dots , x_m)$ denote a permutation of the integers $1, 2, \cdots , m$ . Let $f(x) = x_1n_1 + x_2n_2 + ... + x_mn_m$ . Show that for some distinct permutations $a$ , $b$ the difference $f(a) - f(b)$ is a multiple of $m!$ .

Solution

On the other hand, using the fact that $f(x)=x_1n_1 + x_2n_2 + ... + x_mn_m$ , we can combine the terms with the same coefficient ( $n_i$ ). For each $n_1$ , since all the $v_j$ are distinct, the coefficient in the sum would be $\sum x_i$ over all permutations $x$ of $\{1,2,...,m\}$ . Thus, the coefficient would be $\sum_{i=1}^m i(m-1)!=\frac{m!(m+1)}{2}$ . Since $m$ is odd, $\frac{m+1}{2}$ is an integer, so the coefficient is congruent to $0\pmod{m!}$ . Thus, the whole sum is congruent to $0\pmod{m!}$ . Therefore, $\frac{m!(m!-1)}{2}\equiv0\pmod{m!}$ . But, since $m>1$ , we have $m!$ is even, and thus $m!-1$ is odd. Therefore, the integer $\frac{m!(m!-1)}{2}$ has one factor of $2$ less than $m!$ does. Contradiction!