International Mathematical Olympiad Shortlisted Problems

Answer. There are two such functions: $f(n)=n+1$ for all $n\in {\mathbb{Z}}_{⩾0}$, and $$f(n)=\{\begin{array}{ll}n+1,& n\equiv 0(\mathrm{mod}4)\text{ or }n\equiv 2(\mathrm{mod}4),\\ n+5,& n\equiv 1(\mathrm{mod}4),\\ n-3,& n\equiv 3(\mathrm{mod}4)\end{array}\text{ for all }n\in {\mathbb{Z}}_{⩾0}$$ Throughout all the solutions, we write $h^k(x)$ to abbreviate the $k$th iteration of function $h$, so $h^0$ is the identity function, and $h^k(x)=\underset{k\text{ times}}{\underbrace{h(\dots h}}(x)\dots ))$ for $k⩾1$.

Solution 1. To start, we get from () that $$f^4(n)=f(f^3(n))=f(f(n+1)+1)\text{ and }{f}^4(n+1)=f^3(f(n+1))=f(f(n+1)+1)+1$$ thus $$\begin{array}{c}{f}^4(n)+1=f^4(n+1)\end{array}\text{\hspace{1em}(2)}$$ I. Let us denote by $R_i$ the range of $f^i$; note that $R_0={\mathbb{Z}}_{⩾0}$ since $f^0$ is the identity function. Obviously, $R_0\supseteq R_1\supseteq \dots$. Next, from (2) we get that if $a\in R_4$ then also $a+1\in R_4$. This implies that ${\mathbb{Z}}_{⩾0}\backslash R_4$ - and hence ${\mathbb{Z}}_{⩾0}\backslash R_1$ - is finite. In particular, $R_1$ is unbounded. Assume that $f(m)=f(n)$ for some distinct $m$ and $n$. Then from $(\ast )$ we obtain $f(m+1)=f(n+1)$; by an easy induction we then get that $f(m+c)=f(n+c)$ for every $c⩾0$. So the function $f(k)$ is periodic with period $|m-n|$ for $k⩾m$, and thus $R_1$ should be bounded, which is false. So, $f$ is injective. II. Denote now $S_i=R_{i-1}\backslash R_i$; all these sets are finite for $i⩽4$. On the other hand, by the injectivity we have $n\in S_i⟺f(n)\in S_{i+1}$. By the injectivity again, $f$ implements a bijection between $S_i$ and $S_{i+1}$, thus $\left|S_1\right|=\left|S_2\right|=\dots$; denote this common cardinality by $k$. If $0\in R_3$ then $0=f(f(f(n)))$ for some $n$, thus from () we get $f(n+1)=-1$ which is impossible. Therefore $0\in R_0\backslash R_3=S_1\cup S_2\cup S_3$, thus $k⩾1$. Next, let us describe the elements $b$ of $R_0\backslash R_3=S_1\cup S_2\cup S_3$. We claim that each such element satisfies at least one of three conditions (i) $b=0$, (ii) $b=f(0)+1$, and (iii) $b-1\in S_1$. Otherwise $b-1\in {\mathbb{Z}}_{⩾0}$, and there exists some $n>0$ such that $f(n)=b-1$; but then $f^3(n-1)=f(n)+1=b$, so $b\in R_3$. This yields $$3k=\left|S_1\cup S_2\cup S_3\right|⩽1+1+\left|S_1\right|=k+2$$ or $k⩽1$. Therefore $k=1$, and the inequality above comes to equality. So we have $S_1=\{a\}$, $S_2=\{f(a)\}$, and $S_3=\left\{f^2(a)\right\}$ for some $a\in {\mathbb{Z}}_{⩾0}$, and each one of the three options (i), (ii), and (iii) should be realized exactly once, which means that $$\begin{array}{c}\left\{a,f(a),f^2(a)\right\}=\{0,a+1,f(0)+1\}\end{array}\text{\hspace{1em}(3)}$$ III. From (3), we get $a+1\in \left\{f(a),f^2(a)\right\}$ (the case $a+1=a$ is impossible). If $a+1=f^2(a)$ then we have $f(a+1)=f^3(a)=f(a+1)+1$ which is absurd. Therefore $$\begin{array}{c}f(a)=a+1\end{array}\text{\hspace{1em}(4)}$$ Next, again from (3) we have $0\in \left\{a,f^2(a)\right\}$. Let us consider these two cases separately. Case 1. Assume that $a=0$, then $f(0)=f(a)=a+1=1$. Also from (3) we get $f(1)=f^2(a)=f(0)+1=2$. Now, let us show that $f(n)=n+1$ by induction on $n$; the base cases $n⩽1$ are established. Next, if $n⩾2$ then the induction hypothesis implies $$n+1=f(n-1)+1=f^3(n-2)=f^2(n-1)=f(n)$$ establishing the step. In this case we have obtained the first of two answers; checking that is satisfies () is straightforward. Case 2. Assume now that $f^2(a)=0$; then by (3) we get $a=f(0)+1$. By (4) we get $f(a+1)=f^2(a)=0$, then $f(0)=f^3(a)=f(a+1)+1=1$, hence $a=f(0)+1=2$ and $f(2)=3$ by (4). To summarize, $$f(0)=1,f(2)=3,f(3)=0$$ Now let us prove by induction on $m$ that (1) holds for all $n=4k,4k+2,4k+3$ with $k⩽m$ and for all $n=4k+1$ with $k<m$. The base case $m=0$ is established above. For the step, assume that $m⩾1$. From ( $\ast$ ) we get $f^3(4m-3)=f(4m-2)+1=4m$. Next, by (2) we have $$f(4m)=f^4(4m-3)=f^4(4m-4)+1=f^3(4m-3)+1=4m+1$$ Then by the induction hypothesis together with () we successively obtain $$\begin{array}{rl}& f(4m-3)=f^3(4m-1)=f(4m)+1=4m+2\\ & f(4m+2)=f^3(4m-4)=f(4m-3)+1=4m+3\\ & f(4m+3)=f^3(4m-3)=f(4m-2)+1=4m\end{array}$$ thus finishing the induction step. Finally, it is straightforward to check that the constructed function works: $$\begin{array}{rlrl}{f}^3(4k)& =4k+7=f(4k+1)+1,& & f^3(4k+1)=4k+4=f(4k+2)+1,\\ f^3(4k+2)& =4k+1=f(4k+3)+1,& & f^3(4k+3)=4k+6=f(4k+4)+1.\end{array}$$

Solution 2. I. For convenience, let us introduce the function $g(n)=f(n)+1$. Substituting $f(n)$ instead of $n$ into () we obtain $$\begin{array}{c}{f}^4(n)=f(f(n)+1)+1,\text{ or }{f}^4(n)=g^2(n)\end{array}\text{\hspace{1em}(5)}$$ Applying $f$ to both parts of () and using (5) we get $$\begin{array}{c}{f}^4(n)+1=f(f(n+1)+1)+1=f^4(n+1)\end{array}\text{\hspace{1em}(6)}$$ Thus, if $g^2(0)=f^4(0)=c$ then an easy induction on $n$ shows that $$\begin{array}{c}{g}^2(n)=f^4(n)=n+c,n\in {\mathbb{Z}}_{⩾0}\end{array}\text{\hspace{1em}(7)}$$ This relation implies that both $f$ and $g$ are injective: if, say, $f(m)=f(n)$ then $m+c=f^4(m)=f^4(n)=n+c$. Next, since $g(n)⩾1$ for every $n$, we have $c=g^2(0)⩾1$. Thus from (7) again we obtain $f(n)\ne n$ and $g(n)\ne n$ for all $n\in {\mathbb{Z}}_{⩾0}$. II. Next, application of $f$ and $g$ to (7) yields $$\begin{array}{c}f(n+c)=f^5(n)=f^4(f(n))=f(n)+c\text{ and }g(n+c)=g^3(n)=g(n)+c.\end{array}\text{\hspace{1em}(8)}$$ In particular, this means that if $m\equiv n(\mathrm{mod}c)$ then $f(m)\equiv f(n)(\mathrm{mod}c)$. Conversely, if $f(m)\equiv f(n)(\mathrm{mod}c)$ then we get $m+c=f^4(m)\equiv f^4(n)=n+c(\mathrm{mod}c)$. Thus, $$\begin{array}{c}m\equiv n(\mathrm{mod}c)⟺f(m)\equiv f(n)(\mathrm{mod}c)⟺g(m)\equiv g(n)(\mathrm{mod}c).\end{array}\text{\hspace{1em}(9)}$$ Now, let us introduce the function $\delta (n)=f(n)-n=g(n)-n-1$. Set $$S=\sum _{n=0}^{c-1}\delta (n)$$ Using (8), we get that for every complete residue system $n_1,\dots ,n_c$ modulo $c$ we also have $$S=\sum _{i=1}^c\delta \left(n_i\right)$$ By (9), we get that $\left\{f^k(n):n=0,\dots ,c-1\right\}$ and $\left\{g^k(n):n=0,\dots ,c-1\right\}$ are complete residue systems modulo $c$ for all $k$. Thus we have $$c^2=\sum _{n=0}^{c-1}\left(f^4(n)-n\right)=\sum _{k=0}^3\sum _{n=0}^{c-1}\left(f^{k+1}(n)-f^k(n)\right)=\sum _{k=0}^3\sum _{n=0}^{c-1}\delta \left(f^k(n)\right)=4S$$ and similarly $$c^2=\sum _{n=0}^{c-1}\left(g^2(n)-n\right)=\sum _{k=0}^1\sum _{n=0}^{c-1}\left(g^{k+1}(n)-g^k(n)\right)=\sum _{k=0}^1\sum _{n=0}^{c-1}\left(\delta \left(g^k(n)\right)+1\right)=2S+2c$$ Therefore $c^2=4S=2\cdot 2S=2\left(c^2-2c\right)$, or $c^2=4c$. Since $c\ne 0$, we get $c=4$. Thus, in view of (8) it is sufficient to determine the values of $f$ on the numbers $0,1,2,3$. III. Let $d=g(0)⩾1$. Then $g(d)=g^2(0)=0+c=4$. Now, if $d⩾4$, then we would have $g(d-4)=g(d)-4=0$ which is impossible. Thus $d\in \{1,2,3\}$. If $d=1$ then we have $f(0)=g(0)-1=0$ which is impossible since $f(n)\ne n$ for all $n$. If $d=3$ then $g(3)=g^2(0)=4$ and hence $f(3)=3$ which is also impossible. Thus $g(0)=2$ and hence $g(2)=g^2(0)=4$. Next, if $g(1)=1+4k$ for some integer $k$, then $5=g^2(1)=g(1+4k)=g(1)+4k=1+8k$ which is impossible. Thus, since $\{g(n):n=0,1,2,3\}$ is a complete residue system modulo 4 , we get $g(1)=3+4k$ and hence $g(3)=g^2(1)-4k=5-4k$, leading to $k=0$ or $k=1$. So, we obtain iether $$f(0)=1,f(1)=2,f(2)=3,f(3)=4,\text{ or }f(0)=1,f(1)=6,f(2)=3,f(3)=0$$ thus arriving to the two functions listed in the answer. Finally, one can check that these two function work as in Solution 1. One may simplify the checking by noticing that (8) allows us to reduce it to $n=0,1,2,3$.