Difference between revisions of "2010 USAJMO Problems/Problem 5"
(Created page with '==Problem== Two permutations <math>a_1, a_2, \ldots, a_{2010}</math> and <math>b_1, b_2, \ldots, b_{2010}</math> of the numbers <math>1, 2, \ldots, 2010</math> are said to inters…') |
(→Solution) |
||
Line 40: | Line 40: | ||
For <math>n = 2010</math> we get <math>m = 1006</math>, which is the required special | For <math>n = 2010</math> we get <math>m = 1006</math>, which is the required special | ||
case of the general result above. | case of the general result above. | ||
+ | |||
+ | == See Also == | ||
+ | {{USAJMO newbox|year=2010|num-b=4|num-a=6}} | ||
+ | |||
+ | [[Category:Olympiad Number Theory Problems]] |
Revision as of 20:14, 28 March 2013
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 |