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.

×

Problem Loading...

Note Loading...

Set Loading...