Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2010 USAJMO Problems/Problem 5"
 
(7 intermediate revisions by the same user not shown)
Line 42: Line 42:
  
 
==Solution 2==
 
==Solution 2==
−
I claim that the permutations:
+
I construct the following permutations by continuously rotating the first 1006 numbers):
  
−
[1, 2, 3 ... 1005, 1006, 1007 ... 2009, 2010]
+
(1, 2, 3 ... 1005, 1006, 1007 ... 2009, 2010)
−
[2, 3, 4 ... 1006, 1, 1007 ... 2009, 2010]
 
−
.
 
−
.
 
−
.
 
−
[1006, 1, 2 ... 1005, 1007, ... 2009, 2010]
 
  
−
satisfy the property that any other permutation will intersect with this.
+
(2, 3, 4 ... 1006, 1, 1007 ... 2009, 2010)
 +
 
 +
...
 +
 
 +
...
 +
 
 +
...
 +
 
 +
(1006, 1, 2 ... 1005, 1007, ... 2009, 2010)
 +
 
 +
 
 +
 
 +
I claim that these permutations above satisfy the property that any other permutation will intersect with at least one of them.
  
 
'''Proof''':
 
'''Proof''':
−
Assume that there exists a permutation that won't intersect with these, say <math>(a_1 ... a_{2010})</math>. If <math>a_k \leq 1006</math>, <math>1 \geq k \geq 1006</math>, we get an intersection. So, for all <math>1 \geq k \geq 1006</math>, <math>2010 \leq a_k > 1006</math>. There are 1004 numbers such that <math>2010 \leq a_k > 1006</math>, but we need to have 1006 numbers to fill in 1006 spots, and thus, by pigeonhole principle(the numbers are the holes, the spots are the pigeons), there must be 2 spots that have the same number! However, in a permutation, all numbers must be distinct, so we have a contradiction.
+
Assume for the sake of contradiction that there exists a permutation that won't intersect with these, say <math>(a_1, a_2, a_3 ... a_{2010})</math>.
 +
 
 +
'''Lemma''':
 +
If there exists a k such that <math>1 \leq k \leq 1006</math> <math>a_k \leq 1006</math>, we will get an intersection with the permutations.  
 +
 
 +
Note that for any 2 distinct permutations in our list, the numbers in kth index must be different, since each permutation is a rotation of an previous permutation. Also, the numbers can't exceed 1006, so, each number must occur exactly once in the kth index.
 +
 
 +
'''End Lemma'''
 +
 
 +
Using the lemma, in order to avoid intersections, we need <math>1007 \leq a_k \leq 2010</math>, for all <math>1 \leq k \leq 1006</math>.
 +
 
 +
But, there are 1004 numbers such that <math>1007 \leq n \leq 2010</math>, but we need to have 1004 numbers to fill in 1006 spots, and thus, by pigeonhole principle(the numbers are the holes, the spots are the pigeons), there must be 2 spots that have the same number! However, in a permutation, all numbers must be distinct, so we have a contradiction.
 +
 +
So, we have shown such a set of permutations exists satisfying that any permutation is guaranteed to intersect one of them, and the proof is complete. <math>\blacksquare</math> 
 +
 
 +
-Alexlikemath
  
−
Thus, such a set of 1006 permutations does exist satisfying that any other permutation does intersect at least 1 of the permutations. Thus, the proof is complete. 
 
 
== See Also ==
 
== See Also ==
 
{{USAJMO newbox|year=2010|num-b=4|num-a=6}}
 
{{USAJMO newbox|year=2010|num-b=4|num-a=6}}

Latest revision as of 21:37, 18 June 2020

Problem

Two permutations $a_1, a_2, \ldots, a_{2010}$ and $b_1, b_2, \ldots, b_{2010}$ of the numbers $1, 2, \ldots, 2010$ are said to intersect if $a_k = b_k$ for some value of $k$ in the range $1 \le k\le 2010$. Show that there exist $1006$ permutations of the numbers $1, 2, \ldots, 2010$ such that any other such permutation is guaranteed to intersect at least one of these $1006$ permutations.

Solution 1

Let $n$ be a positive integer. Let $m$ be the smallest positive integer with $m > n - m$. Since $n > n - n = 0$, $m \le n$. Let $N = \{1, \ldots, n\}$ be the set of positive integers from $1$ to $n$. Let $M \subset N$, be $M = \{1, \ldots, m\}$.

Let $P_n$ be the set of of permutations of $N$.

Let $C_m$ be the set of cyclic permutations of $M$, there are $m$ cyclic permutations in all, and $C_m$ acts transitively on $M$, i.e. for every pair of elements $a,b \in M$, there is an element of $C_m$ that maps $a$ to $b$.

Let $C'_m \subset P_n$ be the permutations in $P_n$ that leave $N\setminus M$ fixed, and restricted to $M$ yield one of the permutations in $C_m$. There is a natural one-to-one correspondence between $C'_m$ and $C_m$.

We claim that the $m$ permutations $C'_m$ intersect every permutation in $P_n$.

Suppose, to the contrary, that there exists a permutation $p \in P_n$ that does not intersect any permutation in $C'_m$. Since $C'_m$ acts transitively on $M \subset N$ the permutation $p$ cannot send any element of $M$ to any other element of $M$, therefore it must send all the elements of $M$ to $N\setminus M$, but since $N\setminus M$ has $n - m$ elements and $m > n - m$, this is impossible by the pigeonhole principle. Therefore such a permutation cannot exist, and the permutations in $C'_m$ intersect every permutation in $P_n$.

For $n = 2010$ we get $m = 1006$, which is the required special case of the general result above.

Solution 2

I construct the following permutations by continuously rotating the first 1006 numbers):

(1, 2, 3 ... 1005, 1006, 1007 ... 2009, 2010)

(2, 3, 4 ... 1006, 1, 1007 ... 2009, 2010)

...

...

...

(1006, 1, 2 ... 1005, 1007, ... 2009, 2010)


I claim that these permutations above satisfy the property that any other permutation will intersect with at least one of them.

Proof: Assume for the sake of contradiction that there exists a permutation that won't intersect with these, say $(a_1, a_2, a_3 ... a_{2010})$.

Lemma: If there exists a k such that $1 \leq k \leq 1006$ $a_k \leq 1006$, we will get an intersection with the permutations.

Note that for any 2 distinct permutations in our list, the numbers in kth index must be different, since each permutation is a rotation of an previous permutation. Also, the numbers can't exceed 1006, so, each number must occur exactly once in the kth index.

End Lemma

Using the lemma, in order to avoid intersections, we need $1007 \leq a_k \leq 2010$, for all $1 \leq k \leq 1006$.

But, there are 1004 numbers such that $1007 \leq n \leq 2010$, but we need to have 1004 numbers to fill in 1006 spots, and thus, by pigeonhole principle(the numbers are the holes, the spots are the pigeons), there must be 2 spots that have the same number! However, in a permutation, all numbers must be distinct, so we have a contradiction.

So, we have shown such a set of permutations exists satisfying that any permutation is guaranteed to intersect one of them, and the proof is complete. $\blacksquare$

-Alexlikemath

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2010_USAJMO_Problems/Problem_5&oldid=125883"