Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2001 IMO Problems/Problem 4"

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

Revision as of 10:09, 8 May 2011

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!

See also

2001 IMO (Problems) • Resources
Preceded by
Problem 3 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 5
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_IMO_Problems/Problem_4&oldid=38406"