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"
Line 61: Line 61:
  
 
'''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 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.
  
 
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.   
 
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.   

Revision as of 12:30, 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 claim that the permutations:

[1, 2, 3 ... 1005, 1006, 1007 ... 2009, 2010]

[2, 3, 4 ... 1006, 1, 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.

Proof: Assume that there exists a permutation that won't intersect with these, say $(a_1 ... a_{2010})$. If $a_k \leq 1006$, $1 \geq k \geq 1006$, we get an intersection. So, for all $1 \geq k \geq 1006$, $2010 \geq a_k > 1006$. There are 1004 numbers such that $2010 \geq a_k > 1006$, 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.

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.

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