74th 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^{\prime },b^{\prime }:S\cup \{n+1\}\to S\cup \{n+1\}$ be analogous to $a$ and $b$. Then $((b^{\prime }{)}^{n-m+1}f)(n+1)=n+1$, so the restriction of $g=(b^{\prime }{)}^{n-m+1}f$ to $S$ can be written as a composition of $a$ and $b$; we have $f=(b^{\prime }{)}^{m}g$ (1).

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

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}}^{\ast }$. 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}}^{\ast }$.

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=hc{s}^{-1}{r}^{-1}$ can be expressed as a composition of the functions $a,b,c$.