At above I think you are supposed to state the pigeon hole principle. Once you think of that, this becomes like a 15 minute solve and a 30 minute proof.

I stated that I used the pigeon-hole principle, just to err on the side of safety, although I am not sure whether it was necessary. (I think it would be for a seven.) This problem was definitely the easiest one for me on the USAJMO.

I was basically just like "Assume a set exists which doesn't intersect these permutations. Then all of the integers 1,2,...1006 must go in the last 1004 slots, so they can't all fit."

Hmm, I don't know what they would prefer, so instead of using 1-1006, I had "arbitrary _1, a_2...a_1006". Made it take quite a while to prove there...

it's not exactly the pidgeonhole principle is it? why would you have to state that to get a 7? it's just that you can't fill it all in validly, not that there are 2 that go in the same category or anything.

Pidgeonhole: Assume there is a permutation that doesnt intersect with the first 1006. Then, the integers 1-1006 must go in slots 1007-2010. Since there are 1006 integers and only 1004 places to put them in, at least one place must contain 2 numbers by the pidgeonhole principle.. However, we know that this is not the case , so there is no permutation not intersecting with any of the first 1006.

I do not understand this at all. Doesn't 1, 2, 3, 4, 5, 6, ..., 2009, 2010 2, 3, 4, 5, 6, 7, ..., 2010, 1 3, 4, 5, 6, 7, 8, ..., 1, 2 ......................................... ......................................... 2009, 2010, 1, 2, 3, ..., 2008 2010, 1, 2, 3, ... 2009 all of these 2010 sequences don't intersect... What am I missing?

@AkshajK: the problem asks to show there EXISTS sequence that satisfies the conditions. That does not necessarily mean all sequences work.

sorry for reviving but how many points would you give this proof? Consider the matrix with 1st column $1$, $2$, ... , $1006$; 2nd column $1006$, $1$, $2$, ... , $1005$; 3rd column $1005$, $1006$, ... , $1004$ up to column $1006$. Denote by $e_{r, c}$ as the element in row $r$ and column $c$. Note how our matrix is formed: $e_{r,c}$ is taken to $e_{(r+1) \pmod{1006}, c+1}$. Define $R_j$ as the sequence $R_j=(e_{j, 1}, e_{j, 2}, ... , e_{j, 1006})$. Now consider an arbitrary permutation of $(1, 2, ... , 2010)$. Within the first $1006$ terms of such a permutation there must exist at least $1006-(2010-1007+1)=2$ terms that are less than or equal to $1006$. Next, define $Q_j$ as a permutation of $(1, 2, ... , 2010)$ which has its first $1006$ terms as $R_j$. By the pigeonhole principle it is obvious that every permutation of $(1, 2, ... , 2010)$ must intersect at least one of $Q_1$, $Q_2$, ... , $Q_{1006}$ within the first $1006$ terms.

^^ I think your proof is pretty much the same as the above people's, just in a different form. I, personally, would give it a 7, though you should probably get some more advice on it from someone else. BTW, LOL guys. Pigeon is not spelled "Pidgeon".

Wait so would you have to cite Pigeonhole for a 7, or could you just say that, after constructing the permutations, "If any of the terms in the first 1006 of the construction is repeated in any new sequence, it must intersect with one of the <above> sequences because, in the constructed sequences, each of the first 1006 terms is in all of the first 1006 spots. However, because there are only 1004 other terms, at least 1 must be repeated in the first 1006, which gives the desired result."

You don't have to explicitly say "Pigeonhole" to get a 7. As long as you write is correct and understandable, like what you wrote above, the grader will give you full points.

Consider the permutations where 1007,1008,...2010 are always the last 1004 numbers in the permutation, 1,2,3,..,1006... 2,3,4,...,1006,1... etc. where each of the first 1006 positive integers gets a chance to be in each of the first 1006 slots. If there does exist a permutation that doesn't intersect it that would imply that all of the first 1006 positive integers are in the last 1004 numbers because if they were in the first 1006 then it would intersect. This is clearly impossible.

I was wondering if 1006 is the best bound, that is, ¿for every 1005 permutations is it possible to find another which does not intersect any of them? I have been thinking it for a while but I do not get an answer. Any help would be great.

1006 is best possible. Try to prove it using Hall marriage lemma.

Going on v_Enhance's suggestion to show that 1006 is the best possible sized set of permutations: it suffices to show that there always exists a non-intersecting permutation given 1005 permutations; having this fact, if $m < 1005$ permutations are given, we can just add any other $1005 - m$ permutations and use a non-intersecting permutation for this new set of $1005$. So for a collection $\mathcal{P}$ of $1005$ permutations of $[2010]$, form a bipartite graph $G$ with branches $A$ and $B$ having vertices $a_1, a_2, \ldots, a_{2010}$ and $b_1, b_2, \ldots, b_{2010}$. Connect $a_i$ to $b_j$ if and only if there does not exist $\pi \in \mathcal{P}$ with $\pi(i) = j$. A perfect matching in $G$ would yield a non-intersecting permutation $\sigma$ by choosing $\sigma(i)$ to be $k$ such that $\overline{a_i b_k}$ appears in the perfect matching, so it suffices to show that $G$ contains a perfect matching. Since any $j \in [2010]$ only appears in at most $1005$ positions in the permutations of $\mathcal{P}$ (i.e. there are at most $1005$ $i$'s such that $\pi(i) = j$ for some $\pi \in \mathcal{P}$), this leaves at least $1005$ positions for $j$ not to appear in, i.e. $|N_G(\{a_i\})| \ge 1005$ for all $i$, so $|N_G(S)| \ge |S|$ for all (non-empty) subsets of $A$ with size at most $1005$ (and for $S = \varnothing$, $|N_G(S)| = 0 = |S|$). For $S \subseteq A$ with $|S| \ge 1006$, and any $j$, at least one of the $a_i$'s in $S$ is such that $\pi(i) \neq j$ for all $\pi \in \mathcal{P}$ since $|\mathcal{P}|$ is only $1005$. So there exists $a_i \in S$ such that $\overline{a_i b_j}$ appears in $G$, i.e. $|N_G(S)| = 2010 \ge |S|$. So in all cases $|N(S)| \ge |S|$ so by Hall's Marriage Condition there is a perfect matching of $G$.

Consider the $1006$ permutations as a $1006$ by $2010$ array. Now take $1006$ of the $2010$ columns and put the numbers $(1,2,3,\dots 1006)$ (it doesn't matter which numbers really) into each of the columns. Now, we are left with $1006$ numbers that must be placed into $1004$ columns. Impossible, hence we are done. $\square$

Sorry for the bump.

Consider the permutations: $1,2,\ldots,1006,1007,1008,\ldots,2010$ $2,3,\ldots,1,1007,1008,\ldots,2010$ $3,4,\ldots,2,1007,1008,\ldots,2010$ And so on, until: $1006,1,\ldots,1005,1007,1008,\ldots,2010$ Where the first $1006$ numbers "loop" and the rest remain constant. We see that, by pigeonhole, there must be at least one (actually two, but it doesn't matter) number in $\{1,2,\ldots,1006\}$ which is not in the last $2010-1006=1004$ elements in the permutation, and is therefore in the first $1006$. Since every number in $\{1,2,\ldots,1006\}$ occupies every position from 1st to 1006th in one of the 1006 permutations we chose, it follows that any permutation must intersect with at least one of the 1006 permutations we chose. $\blacksquare$

Cool problem. Construction: Pick $S\subseteq \{1,2,...,2010\}$ with $|S|=1004$. Let $Q$ be the set of elements in $\{1,2,...,2010\}\notin S$. Clearly $|Q|=1006$. Suppose the said permutations are $b_1, b_2,..., b_{1006}$. For each set $\mathcal{A}_i$, pick $\mathcal{A}_{i_n}$ to be the $n$th element in $\mathcal{A}_i$(matrix style ). Pick $b_{i_j}=S_{j-1006}\forall 1007\le j\le 2010$. Define the $k$th loop of a permutation of $\{1,...,n\}$ to be some $\{k,...,n,1,...,k-1\}$ with $n\ge k\ge 1$. Set the first $1006$ elements of $b_i$ to be the $i$th loop of $Q$. Proof that the construction is valid: From pigeonhole, there exists an element $\epsilon$ of $Q$ such that $\epsilon$ is in one of $b_{i_j}$ with $1\le j\le 1006$. But, with our construction, in each of the first $1006$ columns of some $b_i$, each of the numbers in $Q$ exists. Since $\epsilon$ is also an element of $Q$, there must be an intersection, so we're done.

Make the first 1006 elements of these sets some permutation of {1,2,..., 1006}, which is clearly achievable. Then 1,2,...,1006 must go in the final 1004 slots for any other permutation to not intersect, but this is not possible.

For each of the $1006$ permutations, let the first $1006$ numbers be cyclic shifts of each other, basically such that the first one starts with $1,2,3...,1006$, the second starts with $2,3,4,5....,1006$ and so on until the 10006th one starts with $1006,1005,....,2,1$. The rest of the permutations can be arbitrarily chosen. Observe that for any number in $1,2,3...,1006$, it appears in every possible position from $1$ to $1006$. Now, suppose FTSOC that there is a permutation that does not intersect any of these. Since none of the first $1006$ numbers can appear in any of the first $1006$ positions, they must all appear later. But there are only $1004$ remaining positions and therefore it is impossible

Let our $1006$ permutations be of the form $$(m_1, m_2, \ldots, m_{1006}, 1007, 1008, \ldots, 2010)$$where $$(m_1, m_2, \ldots, m_{1006}) = (1, 2, \ldots, 1006); (2, 3, \ldots, 1006, 1); (3, 4, \ldots, 1006, 1, 2);$$$$\ldots; (1006, 1, 2, \ldots, 1005).$$For the sake of contradiction, assume there exists a permutation $P_n$ of $1, 2, \ldots, 2010$ that doesn't intersect any of these $1006$ permutations. Observe that for the first $1006$ terms of $P_n$, the only possible numbers for each term are $$1007, 1008, \ldots, 2010.$$Since the cardinality of $\{1007, 1008, \ldots, 2010\}$ is $1004$, however, we know at least $1$ number will appear twice throughout the first $1006$ terms of $P_n$ by Pigeonhole. This contradicts the definition of a permutation, so we conclude all permutations of $1, 2, \ldots, 2010$ are guaranteed to intersect at least $1$ of our $1006$ permutations. $\blacksquare$ Remark: Once you realize $\frac{2010}{2} + 1 = 1006$ (probably) matters, it's easy to come up with an inductive argument where you have $2k$ terms and $k+1$ permutations (for $k \ge 2$). Then, some experimentation with small values of $k$ motivates the construction of our aforementioned group of permutations. (Pigeonhole is just a succinct and formal way of stating our logic.) Example: For $k=3$, you can let the $4$ permutations be $$(1, 2, 3, 4, 5, 6); (2, 3, 4, 1, 5, 6); (3, 4, 1, 2, 5, 6); (4, 1, 2, 3, 5, 6).$$

Define the expression $P$ $\gamma$ $Q$ that appends permutation $Q$ to the end of permutation $P$. Let $P_i$ where $1 \le i \le 1006$ be the $1006$ permutations. For $1 \le i \le 1006$ denote $M_i$ as an arbitrary permutation of $(1,2,...,1006)$ that doesn't intersect any other $M_i$ and $N_i$ as an arbitrary permutation of $(1007,1008,...,2010)$ that doesn't intersect any other $N_i$. Without losing generality, we can assume $P_i = $ $M_i$ $\gamma$ $N_i$ for $1 \le i \le 1006$. For the sake of contradiction, assume there does exist a permutation $Q$ that doesn't intersect any $P_i$. Then the first $1006$ elements of $Q$ must be contained in $S = {1007,1008,...,2010}$. However $|S| = 1004$ so by PHP at least one element in $S$ must repeat in the first $1006$ elements of $Q$, which contradicts the definition of a permutation. $\blacksquare$

USAJMO 2010 Problem 5. Two permutations $(a_1,a_2,\dots,a_{2010})$ and $(b_1,b_2,\dots,b_{2010})$ of the numbers $1,2,\dots,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,\dots,2010$ such that any other such permutation is guaranteed to intersect at least one of these $1006$ permutations. Solution. Consider the permutations: $(1,2,\ldots,1006,1007,1008,\ldots,2010)$ $(2,3,\ldots,1,1007,1008,\ldots,2010)$ $(3,4,\ldots,2,1007,1008,\ldots,2010)$ $\dots$ $(1006,1,\ldots,1005,1007,1008,\ldots,2010)$ Now for any permutation by PP there exists a number in $\{1,2,\ldots,1006\}$ in one of the first $1006$ places, this clearly finish.

Use the 1006 rows of the following matrix: \[ \begin{bmatrix} 1&2&3&\cdots&1005&1006&1007&\cdots&2010 \\ 2&3&4&\cdots&1006&1&1007&\cdots&2010 \\ 3&4&5&\cdots&1&2&1007&\cdots&2010 \\ \vdots&\vdots&\vdots&&\vdots &\vdots&\vdots&&\vdots \\ 1006&1&2&\cdots&1004&1005&1007&\cdots&2010 \end{bmatrix} \]Consider any permutation $\sigma$ of $(1,\ldots,2010)$. We must have at least one of $1,2,\ldots,1006$ appear in the first $1006$ entries of $\sigma$ by Pigeonhole, since there are only $1004$ entries after the first $1006$. Then, there will be some intersection, since leftmost $1006\times 1006$ matrix of the above is all cyclic shifts of $(1,\ldots,1006)$. Motivation: Basically we want to compactly detect numbers. The idea is the following: we are trying to construct the $1006\times 2010$ matrix. Say the entries that 1 appears in are $\{x_1,\ldots,x_{1006}\} \subseteq \{1,\ldots,2010\}$; call this the set of detection for 1. Then 1 must be detected in these columns of the matrix. First I was trying to use different sets of detection for different numbers, but then we can construct ``bad'' permutations. The main idea is to use \textbf{one} set of detection for multiple numbers. This gives us a lot more information about this set; using multiple sets, we get no information. Cyclic shift is a good way to construct this; it covers everything.

Consider the $1006$ permutations the rows of the matrix \[\begin{bmatrix} 1 & 2 & 3 & \ldots & 1005 & 1006 & 1007 & 1008 & \ldots & 2010 \\ 2 & 3 & \ldots & 1005 & 1006 & 1 & 1007 & 1008 & \ldots & 2010 \\ 3 & 4 & \ldots & 1006 & 1 & 2 & 1007 & 1008 & \ldots & 2010 \\ \vdots & \vdots & & \vdots & \vdots & \vdots & \vdots & \vdots & & \vdots \\ 1005 & 1006 & 1 & 2 & \ldots & 1004 & 1007 & 1008 & \ldots & 2010 \\ 1006 & 1 & 2 & \ldots & 1004 & 1005 & 1007 & 1008 & \ldots & 2010 \\ \end{bmatrix}\] Suppose there exists a permutation intersects one of these. Note that in each of the first $1006$ positions, each number from $1$ to $1006$ is covered, so everything from $1$ to $1006$ must be in the last $2010-1006=1004$ positions, a contradiction as $1004<1006$.

Let the $1006$ permutations take on the form of $a_1,a_2,\dots,a_{1006},1007,1008,\dots,2010$, where $a_1,a_2,\dots,a_{1006}$ varies across the $1006$ "cycles" of $1,2,\dots,1006$. The first few such cycles are $1,2,\dots,1006$, $2,3,\dots,1006,1$, and $3,4,\dots,1006,1,2$. In these permutations, each of the numbers from $1$ to $1006$ take on each of positions $1$ to $1006$ in the permutation. Hence, if FTSOC there were some permutation of $1,2,\dots,2010$ that intersected with none of the $1006$ mentioned permutations, none of $1,2,\dots,1006$ could appear in positions $1$ to $1006$, so they would all have to fit into positions $1007$ to $2010$. But there are only $1004$ such positions, which can't fit the $1006$ numbers from $1$ to $1006$, contradiction. $\blacksquare$

IAmTheHazard wrote: Consider the permutations: $1,2,\ldots,1006,1007,1008,\ldots,2010$ $2,3,\ldots,1,1007,1008,\ldots,2010$ $3,4,\ldots,2,1007,1008,\ldots,2010$ And so on, until: $1006,1,\ldots,1005,1007,1008,\ldots,2010$ Where the first $1006$ numbers "loop" and the rest remain constant. We see that, by pigeonhole, there must be at least one (actually two, but it doesn't matter) number in $\{1,2,\ldots,1006\}$ which is not in the last $2010-1006=1004$ elements in the permutation, and is therefore in the first $1006$. Since every number in $\{1,2,\ldots,1006\}$ occupies every position from 1st to 1006th in one of the 1006 permutations we chose, it follows that any permutation must intersect with at least one of the 1006 permutations we chose. $\blacksquare$ can't we just write he answer as $1,2,\ldots,1006,1007,1008,\ldots,2010$ $2,3,\ldots,1,1007,1008,\ldots,2010$ $3,4,\ldots,2,1007,1008,\ldots,2010$ And so on, until: $1006,1,\ldots,1005,1007,1008,\ldots,2010$? because the problem said to proof that there exists so cant we just write this?

David_Kim_0202 wrote: IAmTheHazard wrote: Consider the permutations: $1,2,\ldots,1006,1007,1008,\ldots,2010$ $2,3,\ldots,1,1007,1008,\ldots,2010$ $3,4,\ldots,2,1007,1008,\ldots,2010$ And so on, until: $1006,1,\ldots,1005,1007,1008,\ldots,2010$ Where the first $1006$ numbers "loop" and the rest remain constant. We see that, by pigeonhole, there must be at least one (actually two, but it doesn't matter) number in $\{1,2,\ldots,1006\}$ which is not in the last $2010-1006=1004$ elements in the permutation, and is therefore in the first $1006$. Since every number in $\{1,2,\ldots,1006\}$ occupies every position from 1st to 1006th in one of the 1006 permutations we chose, it follows that any permutation must intersect with at least one of the 1006 permutations we chose. $\blacksquare$ can't we just write he answer as $1,2,\ldots,1006,1007,1008,\ldots,2010$ $2,3,\ldots,1,1007,1008,\ldots,2010$ $3,4,\ldots,2,1007,1008,\ldots,2010$ And so on, until: $1006,1,\ldots,1005,1007,1008,\ldots,2010$? because the problem said to proof that there exists so cant we just write this? oh nevermind. I understood the problem the wrong way.

Got the same solution as most people So the construction is 1, 2, 3, ..., 1006, 1007, 1008, ..., 2010 2, 3, 4, ..., 1006, 1, 1007, 1008, ..., 2010 ... 1006, 1, 2, ..., 1004, 1005, 1007, 1008, 2010 And all numbers 1 to 1006 cover every single one of the first 1006 positions, if a permutation does not intersect, its numbers 1 to 1006 must all fit in the last 1004 positions, impossible by Pigeonhole Principle. Full proof here: https://infinityintegral.substack.com/p/usajmo-2010-contest-review

Here’s our construction: take $1, 2,\dots, 2010$ and “loop” it around, so that the permutations are \begin{align*} 1, 2, \dots, 2010 \\ 2, 3, \dots, 2010, 1 \\ 3, 4, \dots, 2010, 1, 2 \\ \dots \\ 1006, 1007, \dots, 2010, 1, 2,\dots, 1005. \end{align*}The first numbers in every row are $1$, $2$, $3$, $\dots$, $1006$. If we were able to pick a non-intersecting permutation, its elements must fit in one of the $1004$-element “avoiding” subsets. But that’s impossible, therefore any other permutation must intersect. $\square$

I claim the answer is yes. We "cycle" these permutations so that the first $1006$ terms of these $1006$ permutations are as follows (the other $1004$ numbers don't matter make them whatever you want); \[1, 2, \dots, 1006,\]\[2, 3, \dots, 1006, 1,\]\[\dots,\]\[1006, 1, \dots, 1005,\]which gives for a total of $1006$ permutations. This works because over all of these permutations, each of the $1006$ numbers $1$, $2$, $\dots$, $1006$ appears in each of the first $1006$ spots once. Additionally, by Pigeonhole Principle, we must have that at least one of the first $1006$ numbers must appear in one of the first $1006$ positions (Assume FTSOC not, then your $1006$ numbers must all be in the last $1004$ spots, a contradiction). Therefore, any permutation must share at least one number with one of these $1006$ permutations since over all of these permutations, each of the $1006$ numbers $1$, $2$, $\dots$, $1006$ appears in each of the first $1006$ spots once, finishing the problem.

Just wondering, is there a probabilistic approach to this one. And sorry to revive an old one

By checking using greedy algorithms, we are motivated to form 2 cases:- Let $S = {a_1, a_2, \ldots, a_{1006}}$ Case-1 - ${1,2,\ldots, 1006}$ $\in$ $S$ Now here, we observe that the constructed $sequences$, {1,2,3$\ldots$, 1005, 1006,1007,$\ldots$,2010} {2,3$\ldots$, 1006, 1, 1007,$\ldots$,2010} {3, 4$\ldots$, 1, 2, 1007,$\ldots$,2010} $\cdots$ $\cdots$ {1006, 1, $\ldots$, 1004, 1005, 1007, $\ldots$, 2010} Works as for any permutation satisfying the case will have at least one common element with our $sequences$. \emph{Case-2} - {1,2,$\ldots$,1006} $\notin$ $S$ But Now, this case is impossible, we will prove why, If none of the {1,2,$\ldots$,1006} elements belong to $S$, then that means that the $1006$ numbers are in 1004 places ($2010-1006=1004$), which by the $Pigeon Hole Principle$ is only possible if two numbers are in the same spot, which is absurd. Hence this states that $\exists$ atleast one number in $S$, which satisfies the sequences said before $\mathbb{QED}$ $\blacksquare$