IMC 1998 · Problem 2

Prove that the following proposition holds for $n = 3$ (5 points) and $n = 5$ (7 points), and does not hold for $n = 4$ (8 points).

"For any permutation $\pi_1$ of $\{1, 2, \dots, n\}$ different from the identity there is a permutation $\pi_2$ such that any permutation $\pi$ can be obtained from $\pi_1$ and $\pi_2$ using only compositions (for example, $\pi = \pi_1 \circ \pi_1 \circ \pi_2 \circ \pi_1$)."