2010 USAJMO Problems/Problem 5

Revision as of 13:21, 18 June 2020 by Alexlikemath (talk | contribs)

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]

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.

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