Let $S=\{1, 2, 3, \dots 2021\}$ and $f:S \to S$ be a function such that $f^{(n)}(n)=n$ for each $n \in S$. Find all possible values for $f(2021)$. (Here, $f^{(n)}(n) = \underbrace{f(f(f\dots f(}_{n \text{ times} }n)))\dots))$.) Proposed by Viktor Simjanoski
Problem
Source: 2021 Macedonian Team Selection Test P4
Tags: combinatorics, algebra
31.05.2021 01:04
Define $ord(n):=\min \{k\in \mathbb{Z}^+| f^k(n)=n\}$, i.e. the minimal period of the sequence $n,f(n),f^2(n),...$ (its orbit). It is pretty easy to see that $ord(n)|n$, and also $ord(n)$ divides every number in the orbit of $n$. Therefore, we have $ord(2021)|2021=43\cdot 47$. We have four possibilities: 1) $ord(2021)=1$. This is easily achievable only by setting $f(n)=n$ 2)$ord(2021)=2021$. This is impossible because $f(1)=f^1(1)=1$ 3)$ord(2021)=47$. There should be $47$ elements in the orbit of $2021$ all divisible by $47$, but this is impossible since there are only $43$ multiples of $47$ less than or equal to $2021$. 4)$ord(2021)=43$. In this way we can achieve $f(2021)=43m$ (and only this values) in the following way: take $43$ distinct multiples of $43$ in the order $43m_1=2021, 43m_2=43m, 43m_3,...,43m_{43}$ (they exist since there are $47\geq 43$ multiples of $43$ $\leq 2021$) and define $f(43m_k)=43m_{k+1}$ ($k$ is taken $\pmod{43}$), and $f(n)=n$ otherwise. This works since there are many $1$-orbits and one $43$-orbit of numbers divisible by $43$. In conclusion the set of all possible values achievable by $f(2021)$ is the set of multiples of $43$