Bulgarian National Mathematical Olympiad

Denote by () the condition $f(n)=n-f(f(n-1))$ for any $n\ge 2$. First, we shall prove by induction that

$$f(n)\le f(n+1)\le f(n)+1\text{ for any }n.$$

1. If $n=1$, then $f(2)=2-f(f(1))=1$ and the inequalities hold.

2. Let the inequalities be true for any $k\le n$. Then $f(n+1)=f(n)$ or $f(n)+1$. It follows by () that $f(n)<n$ and the induction hypothesis implies

$$\begin{array}{rl}f(f(n))& \le f(f(n+1))\stackrel{(\ast )}{\Rightarrow }n+1-f(n+1)\le n+2-f(n+2)\\ & \Rightarrow f(n+2)\le f(n+1)+1,\end{array}$$

$$\begin{array}{rl}f(f(n+1))& \le f(f(n))+1\stackrel{(\ast )}{\Rightarrow }n+2-f(n+2)\le n+1-f(n+1)+1\\ & \Rightarrow f(n+1)\le f(n+2).\end{array}$$

So $f(n+1)\le f(n+2)\le f(n+1)+1$ which completes the induction step.

Now, we shall prove again by induction the equality $f(n+f(n))=n$.

1. If $n=1$, then $f(1+f(1))=f(2)=1$.

2. Assume that $f(n+f(n))=n$ for some $n$. Then

$$\begin{array}{rl}f(f(n+f(n)))=f(n)& \stackrel{(\ast )}{\Rightarrow }n+f(n)+1-f(n+f(n)+1)=f(n)\\ & \Rightarrow f(n+f(n)+1)=n+1.\end{array}$$

Case 1. If $f(n+1)=f(n)$, then $f(n+1+f(n+1))=n+1$.

Case 2. If $f(n+1)=f(n)+1$, then $f(n+1+f(n+1))\stackrel{(\ast )}{=}n+1+f(n+1)-f(f(n+f(n+1)))=n+1+f(n+1)-f(n+f(n)+1)=n+1+f(n+1)-f(n+1)=n+1$.

The problem is solved.