2010 USAJMO Problems/Problem 5

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.

We have constructed a set of 1006 permutations. So, such a permutation exists, and the proof is complete. $\blacksquare$

-Alexlikemath

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

Contents

Problem

Solution 1

Solution 2

See Also