2001 IMO Problems/Problem 4
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 |