Find The Minimum N

For two permutations $$P$$ and $$Q$$ of $$\{1, 2, \cdots , n\},$$ an integer $$x$$ is said to be a common element of $$P$$ and $$Q$$ if $$P(x) = Q(x).$$

Find the last three digits of the smallest positive integer $$N$$ with the following property:

• Whenever $$N$$ distinct permutations of $$\{1, 2, \cdots , 2011\}$$ are chosen, there must exist two of them sharing at least two common elements.

Details and assumptions

• As an explicit example, the permutations $$P = \{2, 4, 5, 3, 1\}$$ and $$Q = \{3, 4, 5, 2, 1\}$$ of $$\{1, 2, \cdots , 5\}$$ share two common elements: $$P(2) = Q(2)$$ and $$P(5)=Q(5)$$ ($$P(x)$$ denotes the $$x^{\text{th}}$$ number of permutation $$P$$).

• You might use the fact that $$2011$$ is a prime.

×