Baltic Way 2024 · Problem 9

Since $S$ is finite, there is a finite set of all functions $\left\{g_{1}, g_{2}, \ldots, g_{k}\right\}$ from $S$ to itself. Consider a function $F$ that assigns to each positive integer $n$ one of these functions such that $f$ is the $n$-th power of the function $F(n)$. So $F$ induces a partition of the set of all positive integers into sets $P_{i}$ consisting of all the integers $n$ such that $F(n)=g_{i}$. For any positive integer $N$, consider the complete graph $K_{N}$ on $N$ vertices labeled 1 through $N$. We will colour the edges of $K_{N}$ in $k$ colours $C_{1}, C_{2}, \ldots, C_{k}$ according to the partition in the following way: If $|x-y|$ lies in $P_{i}$, colour the edge between $x$ and $y$ in the colour $C_{i}$. By Ramsey's theorem we can take $N$ to be large enough that there is a monochromatic triangle in $K_{N}$. This means that there are three integers $x, y$ and $z$ and an index $i$ for which $|x-y|,|y-z|,|z-x| \in P_{i}$. Hence there are three integers $a, b, c \in P_{i}$ such that $a+b=c$. Therefore, some function $g_{i}: S \rightarrow S$ satisfies $f(x)=g_{i}^{a}(x)=g_{i}^{b}(x)=g_{i}^{a+b}(x)$ for each $x \in S$. Hence, $f(f(x))=g_{i}^{a}\left(g_{i}^{b}(x)\right)=g_{i}^{a+b}(x)=f(x)$ for each $x \in S$. Remark: The fact that there is an index $i$ for which $P_{i}$ contains three integers $a, b, c$ such that $a+b=c$ is known as Schur's theorem.

Pick $x \in S$ arbitrarily and denote $y=f(x)$. We need to prove that $f(y)=y$. Let $n=|S|$ and consider the function $g: S \rightarrow S$ such that $f=g^{n!}$. As we must have $g^{n!}(x)=y$, the element $y$ must occur among the first $n$ terms of the sequence $x, g(x), g^{2}(x), \ldots$, i.e., $g^{k}(x)=y$ for some $k<n$. So $g^{n!-k}(y)=y$, or putting it otherwise, $g^{n!-k-1}(g(y))=y$. Like before, we obtain that $y$ must occur among the first $n$ terms of the sequence $g(y), g^{2}(y), \ldots$, i.e., $g^{l}(y)=y$ for some $l \leq n$. So certainly $g^{n!}(y)=y$ as $l \mid n$ !. This proves the claim.