Annual Harvard-MIT Mathematics Tournament

Solution:
Answer: 2

Note that both $f$ and $g$, when written in cycle notation, must contain exactly one cycle that contains more than 1 element. Assume $f$ has $k$ fixed points, and that the other $2012-k$ elements form a cycle, (of which there are $(2011-k)!$ ways).

Then note that if $f$ fixes $a$ then $f(g(a))=g(f(a))=g(a)$ implies $f$ fixes $g(a)$. So $g$ must send fixed points of $f$ to fixed points of $f$. It must, therefore, send non-fixed points to non-fixed points. This partitions $S$ into two sets, at least one of which must be fixed by $g$, since $g$ is a perfectutation.

If $g$ fixes all of the non-fixed points of $f$, then, since any function commutes with the identity, $g$ fixes some $m$ of the fixed points and cycles the rest in $(k-m-1)!$ ways. So there are $\sum_{m=0}^{k-2}\binom{k}{m}(k-m-1)!$ choices, which is $\sum_{m=0}^{k-2} \frac{k!}{(k-m) m!}$.

If $g$ fixes all of the fixed points of $f$, then order the non-fixed points of $f$ $a_{1}, a_{2}, \ldots, a_{2012-k}$ such that $f\left(a_{i}\right)=a_{i+1}$. If $g\left(a_{i}\right)=a_{j}$ then $f\left(g\left(a_{i}\right)\right)=a_{j+1}$ thus $g\left(a_{i+1}\right)=a_{j+1}$. Therefore the choice of $g\left(a_{1}\right)$ uniquely determines $g\left(a_{i}\right)$ for the rest of the $i$, and $g\left(a_{m}\right)=a_{m+j-i}$. But $g$ has to be a perfectutation, so $g$ cycles through all the non-fixed points of $f$, which happens if and only if $j-i$ is relatively prime to $2012-k$. So there are $\phi(2012-k)$ choices.

Therefore for any $f$ there are $\sum_{m=0}^{k-2} \frac{k!}{(k-m) m!}+\phi(2012-k)$ choices of $g$, but one of them will be $g=f$, which we cannot have by the problem statement. So there are $-1+\sum_{m=0}^{k-2} \frac{k!}{(k-m) m!}+\phi(2012-k)$ options.

Now note that a permutation can not fix all but one element. So
$$n=\sum_{k=0}^{2010}\binom{2012}{k}(2011-k)!\left(-1+\sum_{m=0}^{k-2} \frac{k!}{(k-m) m!}+\phi(2012-k)\right)$$
Modulo 2011 (which is prime), note that all terms in the summand except the one where $k=1$ vanish. Thus, $n \equiv (2010)!(-1+(-1)) \equiv 2 \pmod{2011}$ by Wilson's Theorem.