Find The Minimum N

Throughout this solution, unless otherwise specified, a permutation will refer to a permutation of $\{1, 2, \cdots , 2011\}.$

Let $A$ be the largest set of permutations any two of which share one common element at most. Also, let $B$ be the largest set of permutations of $\{1, 2, \cdots , 2011\}$ any two of which share at least two common elements.

---

Claim 1: For any pairwise distinct permutations $P, Q, R, S$ where $P, R \in A$ and $Q, S \in B,$ $P \odot R \neq Q \odot S$ (where $\odot$ denotes the composition of two permutations).

Proof: It suffices to show that there exists an $x$ such that $P \odot R (x) \neq Q \odot S(x).$ Note that $P$ and $Q$ share more common elements than $R$ and $S,$ so there must exist an $x$ such that $P(x) = Q(x)$ and $R(x) \neq S(x).$ For this selection of $x,$ we have $P \odot R (x) \neq Q \odot S(x),$ as desired. $\blacksquare$

---

Claim 2: $|A| \times |B| \leq 2011!$

Proof: Our objective is to establish an injection between $|A \times B|$ and the set of permutations. For any two permutations $P, Q$ where $P \in A$ and $Q \in B,$ $P \odot Q$ also forms a permutation. Our first claim shows that distinct choices of $(P, Q)$ correspond to distinct permutations. Hence, $|A \times B| \leq 2011! \implies |A| \times |B| \leq 2011!.$ $\blacksquare$

---

Claim 3: $|B| \geq (2011-2)!$

Proof: Consider the set of permutations $P$ satisfying $P(1) = 1, P(2) = 2.$ Once two elements are fixed, there are $(2011-2)!$ possibilities remaining for $P,$ any two of which share two common elements. $\blacksquare$

---

Claim 4: $|A| \geq 2011 \cdot 2010$

Proof: For all $i, j,$ define the set $\sigma_{i, j} = \{ix+j \pmod{2011}\}_{x=1}^{2011}$ (where $X \pmod {n}$ denotes the remainder when $X$ is divided by $n$ ).

First, we shall show that whenever $2011 \nmid i,$ $\sigma_{i, j}$ forms a permutation of $\{1, 2, \cdots , 2011\}.$ Since all $2011$ elements in the set $\sigma_{i,j}$ are between $1$ and $2011$ inclusive, it suffices to show that all these elements are distinct. Suppose, on the contrary, we have $ix+j \equiv iy+j \pmod{2011}$ for some $1 \leq x < y \leq 2011.$ This implies $2011 \mid i(x-y).$ However, since $2011 \nmid i,$ $\gcd (2011, x)=1 \implies 2011 \mid x-y.$ Note that $|x-y| \leq 2010,$ so we must have $x=y.$

Now, we shall show that for any $a, b, c, d \in [1, 2011]$ ( $2011 \nmid a,c$ ) where it is not the case that $a=c$ and $b=d,$ $\sigma_{a, c}$ and $\sigma_{b, d}$ can share at most one common element.

First, suppose $a=c.$ If there exists a common element $x,$ $ax + b \equiv cx + d \pmod{2011} \implies b \equiv d \pmod{2011} \implies b=d$ since $b, d$ both lie between $1$ and $2011$ so $|b-d| \leq 2010.$ This is a contradiction, so there are no common elements in this case.

Now, suppose $a \neq c.$ Suppose there exists a common element $X.$ We have $ax+b \equiv bx+d \pmod{2011} \\ \implies (a-c)x \equiv (d-b) \pmod{2011} \\ \implies x \equiv (d-b)I \pmod{2011},$ where $I$ denotes the multiplicative inverse of $a-c \pmod{2011}$ (which exists because $2011 \nmid a-c$ ). Thus, the residue of $X \pmod{2011}$ is uniquely determined, which uniquely determines $X$ since $X$ lies between $1$ and $2011.$

Now, as $i$ varies from $1$ to $2010$ and $j$ varies from $1$ to $2011,$ we get $2011 \cdot 2010$ such permutations, no two of which share more than one common element by our above argument. $\blacksquare$

---

Combining claims 2, 3, 4 and noting that $2011 \cdot 2010 \times (2011-2)! = 2011!,$ we deduce that $|A| = 2009!$ and $|B| = 2011 \cdot 2010.$ Our desired answer is simply $N = |B|+1 = 2011^2-2011+1,$ whose last three digits are $11^2-11+1 = \boxed{111}.$