Difference between revisions of "2010 USAJMO Problems/Problem 5"

Line 45: Line 45:
  
 
[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]  
.
+
 
.
+
...
.
+
 
 +
...
 +
 
 +
...
 +
 
 
[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 this.
 
satisfy the property that any other permutation will intersect with this.
Line 57: Line 64:
  
 
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.   
 +
 +
-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 12:23, 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 this.

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 \leq a_k > 1006$. There are 1004 numbers such that $2010 \leq 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 (ProblemsResources)
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

Invalid username
Login to AoPS