IMO Hk TST

We consider the following mapping between the set $S$ of all positive integers formed by $n$ $1$'s and $n$ $2$'s and the set $T$ of all positive integers with $n$ digits formed by $1$, $2$, $3$, $4$ such that the numbers of $1$'s and $2$'s are equal.

For each $m \in S$, we can pair up every two consecutive digits of $m$ from left to right. This gives $n$ pairs in total. Then we replace the pairs $11$, $22$, $12$, $21$ by $1$, $2$, $3$, $4$ respectively. If there are $a$, $b$, $c$, $d$ pairs of $11$, $22$, $12$, $21$ respectively, then there are $2a + c + d$ $1$'s and $2b + c + d$ $2$'s in $m$. Thus, we must have $a = b$. This shows the numbers of $1$'s and $2$'s in the image are the same, and so the image belongs to $T$.

Clearly, the mapping is reversible. For each $m \in T$, we just need to replace the digits $1$, $2$, $3$, $4$ in $m$ by $11$, $22$, $12$, $21$ respectively. If there are $a$, $a$, $c$, $d$ copies of $1$, $2$, $3$, $4$ respectively, then there are $2a + c + d$ $1$'s and $2a + c + d$ $2$'s in the image, and so the image belongs to $S$. This shows the mapping is a bijection, and hence
$$f(n) = |S| = |T| = g(n).$$