Problem:
Two permutations and of the numbers are said to intersect if for some value of in the range . Show that there exist 1006 permutations of the numbers such that any other such permutation is guaranteed to intersect at least one of these 1006 permutations.
Solution:
Let us create the following 1006 permutations , the first 1006 positions of which are all possible cyclic rotations of the sequence , and the remaining 1004 positions are filled arbitrarily with the remaining numbers :
We claim that at least one of these 1006 sequences has the same integer at the same position as the initial (unknown) permutation .
Suppose not. Then the set of the first (leftmost) integers in the permutation contains no integers from to . Hence it consists of the 1004 integers in the range from to only. By the pigeon-hole principle, some two of the integers from the permutation must be equal, which is a contradiction: there are not two identical integers in the permutation .
Consequently, the permutation has at last one common element with some sequence and we are done.
This problem was proposed by Gregory Galperin.
The problems on this page are the property of the MAA's American Mathematics Competitions