2. [20] For what positive integers $n$ do there exist functions $f, g:\{1,2, \ldots, n\} \rightarrow\{1,2, \ldots, n\}$ such that for each $1 \leq i \leq n$, either $f(g(i))=i$ or $g(f(i))=i$, but not both?
Answer: $n$ even We claim that this is possible for all even $n$. First, a construction: set $f(2 m-1)=$ $f(2 m)=2 m-1$ and $g(2 m-1)=g(2 m)=2 m$ 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.