2010 USAJMO 5

[stupidityismygam]

Two permutations [unparseable or potentially dangerous latex formula] and [unparseable or potentially dangerous latex formula] of the numbers [unparseable or potentially dangerous latex formula] are said to intersect if [unparseable or potentially dangerous latex formula] for some value of [unparseable or potentially dangerous latex formula] in the range [unparseable or potentially dangerous latex formula] Show that there exist 1006 permutations of the numbers [unparseable or potentially dangerous latex formula] such that any other such permutation is guaranteed to intersect at least one of these 1006 permutations.

[shrig94]

Just make 1006 permutations in which the numbers 1-1006 are shifted one space, last number entering first place and then 1007-2010 are fixed:
aka
1,2,....,1006,1007,...2010
2,3,...,1006,1,1007,...2010
...
1006,1,....1005,1007....2010

In this scenario, none of the numbers 1-1006 can go in the first 1006 spots so we must fit 1006 numbers in the spots used for 1007-2010 which is only a total of 1004 spots. We cannot do this so we are finished.

Easy Pidgeonhole. This Q took me less than 5 minutes, no joke.