Berkeley Math Circle: Monthly Contest 6

Solution:

Suppose there exists a good sequence.
Then for any two $a, b \in \{1, \ldots, n\}$ there is some sequence of functions $g_{1}, \ldots, g_{m}$ such that $g_{m} \circ g_{m-1} \circ \cdots \circ g_{1}$ maps $a$ and $b$ to the same point. Looking at the images $(a, b), \left(g_{1}(a), g_{1}(b)\right), \left(g_{2}\left(g_{1}(a)\right), g_{2}\left(g_{1}(b)\right)\right), \ldots$ and so on, by the pigeonhole principle we can find a subsequence with $m \leq n^{2}$.
By appending $n$ such sequences together, we can collapse all $n$ inputs to the same output.