2010 USAJMO Problems/Problem 5: Difference between revisions

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

@@ Line 42: / Line 42: @@
 ==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''':
-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
 == See Also ==
 {{USAJMO newbox|year=2010|num-b=4|num-a=6}}

2010 USAJMO (Problems • Resources)
Preceded by Problem 4	Followed by Problem 6
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search

2010 USAJMO Problems/Problem 5: Difference between revisions

Revision as of 13:01, 18 June 2020

Contents

Problem

Solution 1

Solution 2

See Also