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

Notice that if $\{0,1,2,...,m!-1\}\not=\{f(1),f(2),f(3),...,f(m!)\}\pmod{m!}$ then by the pigeon hole princible, there must be some $a,b\in\{1,2,...,m!\}$ such that $f(a)\equiv f(b)\pmod{m!}$ as desired. Thus, we must prove that $\{0,1,2,...,m!-1\}\not=\{f(1),f(2),f(3),...,f(m!)\}\pmod{m!}$ . Suppose there was such a situation. Then, since the two sets have the same number of elements, for every $t\in\{0,1,...,m!-1\}$ , there exists a $v\in\{1,2,...,m!\}$ such that $t\equiv f{v}\pmod{m!}$ . So, let $t\equiv f(v_t)\pmod{m!}$ . Consider the sum $f(v_0)+f(v_1)+\cdots+f(v_{m!-1})\pmod{m!}$ . Using the fact that $f(v_t)\equiv t\pmod{m!}$ , we find the sum is congruent to $0+1+\cdots+m!-1=\frac{m!(m!-1)}{2}$ .

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!

2001 IMO (Problems) • Resources
Preceded by Problem 3	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 5
All IMO Problems and Solutions

Page

Toolbox

Search

2001 IMO Problems/Problem 4

Problem=

Solution

See also