Harvard-MIT Mathematics Tournament

Solution:

Answer: $n$ even

We claim that this is possible for all even $n$. First, a construction: set $f(2m-1) = f(2m) = 2m-1$ and $g(2m-1) = g(2m) = 2m$ for $m = 1, \ldots, \frac{n}{2}$. It is easy to verify that this solution works.

Now, we show that this is impossible for odd $n$. Without loss of generality, suppose that $f(g(1))=1$ and that $g(1)=a \Rightarrow f(a)=1$. Then, we have $g(f(a))=g(a)=1$. Consequently, $a \neq 1$. In this case, call $1$ and $a$ a pair (we likewise regard $i$ and $j$ as a pair when $g(f(i))=i$ and $f(i)=j$). Now, to show that $n$ is even it suffices to show that all pairs are disjoint. Suppose for the sake of contradiction that some integer $b \neq a$ is also in a pair with $1$ (note that $1$ is arbitrary). Then, we have $f(g(b))=b$, $g(b)=1$ or $g(f(b))=b$, $f(b)=1$. But we already know that $g(1)=a$, so we must have $f(g(b))=b$, $g(b)=1$. But that would mean that both $f(g(1))=1$ and $g(f(1))=1$, a contradiction.