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"
(→‎Solution 2)
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]
+
(2, 3, 4 ... 1006, 1, 1007 ... 2009, 2010)
  
 
...
 
...
Line 54: Line 54:
 
...
 
...
  
−
[1006, 1, 2 ... 1005, 1007, ... 2009, 2010]
+
(1006, 1, 2 ... 1005, 1007, ... 2009, 2010)
  
−
(constructed by continuously rotating the first 1006 numbers)
 
  
−
satisfy the property that any other permutation will intersect with at least one of these permutations.
+
 
 +
I claim that these permutations 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 \geq a_k > 1006</math>. There are 1004 numbers such that <math>2010 \geq 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 that there exists a permutation that won't intersect with these, say <math>(a_1, a_2, a_3 ... a_{2010})</math>.
 +
 
 +
'''Lemma''':
 +
If <math>a_k \leq 1006</math>, <math>1 \leq k \leq 1006</math>, we get an intersection.  
 +
 
 +
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.
 +
 
 +
Using the lemma, we get that for all <math>1 \geq k \geq 1006</math>,  <math>2010 \geq a_k > 1006</math>.
  
−
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.   
+
But, there are 1004 numbers such that <math>2010 \geq n > 1006</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.
 +
 
 +
Thus, such a set of 1006 permutations does exist satisfying the given conditions. Thus, the proof is complete.   
  
 
-Alexlikemath
 
-Alexlikemath
 +
 
== See Also ==
 
== See Also ==
 
{{USAJMO newbox|year=2010|num-b=4|num-a=6}}
 
{{USAJMO newbox|year=2010|num-b=4|num-a=6}}

Revision as of 13:01, 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 satisfy the property that any other permutation will intersect with at least one of them.

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

Lemma: If $a_k \leq 1006$, $1 \leq k \leq 1006$, we get an intersection.

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.

Using the lemma, we get that for all $1 \geq k \geq 1006$, $2010 \geq a_k > 1006$.

But, there are 1004 numbers such that $2010 \geq n > 1006$, 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.

Thus, such a set of 1006 permutations does exist satisfying the given conditions. Thus, the proof is complete.

-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=125824"