2010 USAJMO Problems/Problem 5
Problem
Two permutations and
of the numbers
are said to intersect if
for some value of
in the
range
. Show that there exist
permutations
of the numbers
such that any other such
permutation is guaranteed to intersect at least one of these
permutations.
Solution
Let be a positive integer. Let
be the smallest positive integer with
. Since
,
. Let
be the set of positive integers from
to
. Let
,
be
.
Let be the set of of permutations of
.
Let be the set of cyclic permutations of
, there are
cyclic permutations in all, and
acts transitively on
, i.e.
for every pair of elements
, there is an element of
that maps
to
.
Let be the permutations in
that leave
fixed, and restricted to
yield one of the permutations in
.
There is a natural one-to-one correspondence between
and
.
We claim that the permutations
intersect every permutation in
.
Suppose, to the contrary, that there exists a permutation
that does not intersect any permutation in
. Since
acts
transitively on
the permutation
cannot send any element of
to any other element of
, therefore it must send all the
elements of
to
, but since
has
elements and
, this is impossible
by the pigeonhole principle. Therefore such a permutation cannot
exist, and the permutations in
intersect every permutation in
.
For we get
, which is the required special
case of the general result above.
See Also
2010 USAJMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |