Difference between revisions of "2001 IMO Problems/Problem 4"
(→Problem) |
Impromptua (talk | contribs) m (→Solution) |
||
Line 3: | Line 3: | ||
==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 | + | 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]] |
Revision as of 19:56, 19 May 2023
Problem
Let be integers where
is odd. Let
denote a permutation of the integers
. Let
. Show that for some distinct permutations
,
the difference
is a multiple of
.
Solution
Notice that if then by the pigeon hole princible, there must be some
such that
as desired. Thus, we must prove that
. Suppose there was such a situation. Then, since the two sets have the same number of elements, for every
, there exists a
such that
. So, let
. Consider the sum
. Using the fact that
, we find the sum is congruent to
.
On the other hand, using the fact that , we can combine the terms with the same coefficient (
). For each
, since all the
are distinct, the coefficient in the sum would be
over all permutations
of
. Thus, the coefficient would be
. Since
is odd,
is an integer, so the coefficient is congruent to
. Thus, the whole sum is congruent to
. Therefore,
. But, since
, we have
is even, and thus
is odd. Therefore, the integer
has one factor of
less than
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 |