Difference between revisions of "2001 IMO Problems/Problem 4"
(→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 11:08, 8 May 2011
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 |