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=)
m (→‎Solution)
 
(3 intermediate revisions by 2 users not shown)
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>.
  
 
==Solution==
 
==Solution==
−
Notice that if <math>\{0,1,2,...,m!-1\}\not=\{f(1),f(2),f(3),...,f(m!)\}\pmod{m!}</math> then by the pigeon hole princible, there must be some <math>a,b\in\{1,2,...,m!\}</math> such that <math>f(a)\equiv f(b)\pmod{m!}</math> as desired.  Thus, we must prove that <math>\{0,1,2,...,m!-1\}\not=\{f(1),f(2),f(3),...,f(m!)\}\pmod{m!}</math>.  Suppose there was such a situation.  Then, since the two sets have the same number of elements, for every <math>t\in\{0,1,...,m!-1\}</math>, there exists a <math>v\in\{1,2,...,m!\}</math> such that <math>t\equiv f{v}\pmod{m!}</math>.  So, let <math>t\equiv f(v_t)\pmod{m!}</math>.  Consider the sum <math>f(v_0)+f(v_1)+\cdots+f(v_{m!-1})\pmod{m!}</math>.  Using the fact that <math>f(v_t)\equiv t\pmod{m!}</math>, we find the sum is congruent to <math>0+1+\cdots+m!-1=\frac{m!(m!-1)}{2}</math>.   
+
Notice that if <math>\{0,1,2,...,m!-1\}\not=\{f(1),f(2),f(3),...,f(m!)\}\pmod{m!}</math> then by the pigeon hole princible, there must be some <math>a,b\in\{1,2,...,m!\}</math> such that <math>f(a)\equiv f(b)\pmod{m!}</math> as desired.  Thus, we must prove that <math>\{0,1,2,...,m!-1\}\not=\{f(1),f(2),f(3),...,f(m!)\}\pmod{m!}</math>.  Suppose there was such a situation.  Then, since the two sets have the same number of elements, for every <math>t\in\{0,1,...,m!-1\}</math>, there exists a <math>v\in\{1,2,...,m!\}</math> such that <math>t\equiv f(v)\pmod{m!}</math>.  So, let <math>t\equiv f(v_t)\pmod{m!}</math>.  Consider the sum <math>f(v_0)+f(v_1)+\cdots+f(v_{m!-1})\pmod{m!}</math>.  Using the fact that <math>f(v_t)\equiv t\pmod{m!}</math>, we find the sum is congruent to <math>0+1+\cdots+m!-1=\frac{m!(m!-1)}{2}</math>.   
  
 
On the other hand, using the fact that <math>f(x)=x_1n_1 + x_2n_2 + ... + x_mn_m</math>, we can combine the terms with the same coefficient (<math>n_i</math>).  For each <math>n_1</math>, since all the <math>v_j</math> are distinct, the coefficient in the sum would be <math>\sum x_i</math> over all permutations <math>x</math> of <math>\{1,2,...,m\}</math>.  Thus, the coefficient would be <math>\sum_{i=1}^m i(m-1)!=\frac{m!(m+1)}{2}</math>.  Since <math>m</math> is odd, <math>\frac{m+1}{2}</math> is an integer, so the coefficient is congruent to <math>0\pmod{m!}</math>.  Thus, the whole sum is congruent to <math>0\pmod{m!}</math>.  Therefore, <math>\frac{m!(m!-1)}{2}\equiv0\pmod{m!}</math>.  But, since <math>m>1</math>, we have <math>m!</math> is even, and thus <math>m!-1</math> is odd.  Therefore, the integer <math>\frac{m!(m!-1)}{2}</math> has one factor of <math>2</math> less than <math>m!</math> does.  Contradiction!
 
On the other hand, using the fact that <math>f(x)=x_1n_1 + x_2n_2 + ... + x_mn_m</math>, we can combine the terms with the same coefficient (<math>n_i</math>).  For each <math>n_1</math>, since all the <math>v_j</math> are distinct, the coefficient in the sum would be <math>\sum x_i</math> over all permutations <math>x</math> of <math>\{1,2,...,m\}</math>.  Thus, the coefficient would be <math>\sum_{i=1}^m i(m-1)!=\frac{m!(m+1)}{2}</math>.  Since <math>m</math> is odd, <math>\frac{m+1}{2}</math> is an integer, so the coefficient is congruent to <math>0\pmod{m!}</math>.  Thus, the whole sum is congruent to <math>0\pmod{m!}</math>.  Therefore, <math>\frac{m!(m!-1)}{2}\equiv0\pmod{m!}</math>.  But, since <math>m>1</math>, we have <math>m!</math> is even, and thus <math>m!-1</math> is odd.  Therefore, the integer <math>\frac{m!(m!-1)}{2}</math> has one factor of <math>2</math> less than <math>m!</math> does.  Contradiction!
 +
 
==See also==
 
==See also==
 
{{IMO box|num-b=3|num-a=5|year=2001}}
 
{{IMO box|num-b=3|num-a=5|year=2001}}
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 19:01, 19 May 2023

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=193262"