Romanian Mathematical Olympiad

Let $fg$ denote the function composition $f \circ g$ (where $f, g \in \mathcal{F}$), and let $(i_1, i_2, \dots, i_p)$ denote the function $f : S \to S$ defined by $f(i_j) = i_{j+1}$ for $j = \overline{1, p-1}$, $f(i_p) = i_1$, and $f(x) = x$ for $x \ne i_1, \dots, i_p$ (where $i_1, \dots, i_p$ are $p \ge 2$ distinct elements of $S$).

a) We use an inductive approach. For $n=3$, $\mathcal{B} = \{a, a^2, b, b^2, ab, ba\}$.

Now, we suppose the property holds for some $n \ge 3$ and we show that it also holds for $n+1$. Let $f : S \cup \{n+1\} \to S \cup \{n+1\}$, $f(n+1) = m$, and let $a', b' : S \cup \{n+1\} \to S \cup \{n+1\}$ be analogous to $a$ and $b$. Then $((b')^{n-m+1}f)(n+1) = n+1$, so the restriction of $g = (b')^{n-m+1}f$ to $S$ can be written as a composition of $a$ and $b$; we have $f = (b')^m g$ (1).

We have $(b'a')(n+1) = n+1$ and the restriction of $b'a'$ to $S$ is $b$. Moreover, $((b')^n a' b')(n+1) = n+1$ and the restriction of $(b')^n a' b'$ to $S$ is $a$. Then from (1), it follows that $f$ can be written as a composition of $a'$ and $b'$.

b) We show that if $\mathcal{G}$ is a generating set for $\mathcal{F}$, then $|\mathcal{G}| \ge 3$.

If $\mathcal{G}$ has at most two elements $f$ and $g$, then:

* If both $f$ and $g$ are bijective, then $\mathcal{G}$ can only generate bijective functions.
* If both $f$ and $g$ are not bijective, then they are not surjective, so $\mathcal{G}$ can only generate non-surjective functions.
* If, for example, $f$ is bijective and $g$ is not bijective, then the bijective functions generated by $\mathcal{G}$ are $f^n$, $n \in \mathbb{N}^*$. In this case, $\mathcal{G}$ cannot generate both $a$ and $b$ because $ab \ne ba$, while $f^m f^p = f^p f^m$ for all $m, p \in \mathbb{N}^*$.

We show that a generating set for $\mathcal{F}$ is $\mathcal{G} = \{a, b, c\}$, where $c : S \to S$, $c(k) = k$ for $k \in S \setminus \{n\}$, and $c(n) = n-1$. We prove that any $f \in \mathcal{F}$ can be written as a composition of $a, b$, and $c$ by descending induction on the number of elements in the image of $f$. If $|\text{Im } f| = n$, then $f$ is bijective and we use (a).

We assume that the statement is true for any $f$ with $|\mathrm{Im} f| = k$, where $1 < k \le n$, and we prove it for an arbitrary $g$ with $|\mathrm{Im} g| = k - 1$. Since $g$ is not injective, there exist $u, v \in S$, $u \ne v$, and a bijective function $r$ such that $\mathrm{Im} gr = \{1, 2, \dots, k-1\}$ and $(gr)(u) = (gr)(v) = k-1$. Let $s : S \to S$ be defined such that $s(n-1) = u$, $s(n) = v$, and $s(x) = x$ for $x \ne u, v$. We consider the function $h : S \to S$ defined as $h(x) = (grs)(x)$ for $x \le n-1$ and $h(n) = k$. Then $|\mathrm{Im} h| = k$, so $h$ can be expressed as a composition of the functions $a, b, c$, and $grs = hc$. Thus, $g = hcs^{-1}r^{-1}$ can be expressed as a composition of the functions $a, b, c$.