3. The set of positive integers coincides with the union of the sets

$$
\{f(1), f(2), \ldots, f(n), \ldots\} \quad \text { and }\{g(1), g(2), \ldots, g(n), \ldots\}
$$

which are disjoint, where

$$
\begin{gathered}
f(1)<f(2)<\cdots<f(n)<\ldots \\
g(1)<g(2)<\cdots<g(n)<\ldots
\end{gathered}
$$

and $g(n)=f(f(n))+1$ for all $n \geqq 1$.

Determine the value of $f(240)$! (United Kingdom, 8 points)
I. solution. Consider the integers between 1 and $g(n)$. Each of these is either a value taken by $f$ or $g$ at some point. Specifically, $g$ takes the value $n$ at $g(1), g(2), \ldots, g(n)$; and based on $g(n)-1=f(f(n))$, $f$ takes the value $f(n)$ at $f(1), f(2), \ldots, f(n)$. This means that every number between 1 and $g(n)$ is obtained exactly once, so

$$
g(n)=f(n)+n
$$

From this, it follows that $f(1)=1$ (since either $f(1)$ or $g(1)$ must be 1, and $g(1)=f(1)+1>1$), hence $g(1)=2$. Similarly, $f(2)=3$ (since $g(2)=f(2)+2>f(1)+2=3$). After this, we can start filling in the following table. Every natural number must appear exactly once. Thus, if we have filled in part of the table, the next column's "f row" should contain the smallest number not yet present, and the "g row" should contain the number according to the (*) formula.

| - | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | $\ldots$ | 234 | 235 | 236 | 237 | 238 | 239 | 240 |
| :--- | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $f$ | 1 | 3 | 4 | 6 | 8 | 9 | 11 | 12 | 14 | 16 | 17 | 19 | 21 | 22 | 24 | 25 | $\ldots$ | 378 | 380 | 381 | 383 | 385 | 386 | 388 |
| $g$ | 2 | 5 | 7 | 10 | 13 | 15 | 18 | 20 | 23 | 26 | 28 | 31 | 34 | 36 | 39 | 41 | $\ldots$ | 612 | 615 | 617 | 620 | 623 | 625 | 628 |

The result can be read from the table: $f(240)=388$.

II. solution. Based on the (*) relationship,

$$
f(f(n))=f(n)+n-1
$$

From this, $f(3)=f(f(2))=f(2)+2-1=4, f(4)=4+3-1=6, f(6)=9, f(9)=14, f(14)=22, f(22)=35, f(35)=56$, and thus $g(35)=56+35=91$. Since every $g(n)$ value is the successor of some $f(k)$ value, $g(36)$ cannot be 92, so $f(57)=92$. From this, $f(92)=92+56=148, f(148)=239, f(239)=386$. On the other hand, $g(148)=239+148=387$, so based on the previous reasoning, $f(240)=388$.

III. solution. Let $a_{0}=1$, and $a_{n+1}+1=f\left(a_{n}+1\right) \quad(n=0,1,2, \ldots)$. Then $a_{1}=2$ and according to the (**) formula,

$$
a_{n+2}+1=f\left(a_{n+1}+1\right)=f\left(f\left(a_{n}+1\right)\right)=a_{n+1}+1+a_{n}
$$

that is, the sequence $\left\{a_{n}\right\}$ is precisely the Fibonacci sequence. We will show by induction that

$(* * *)$

$$
f\left(a_{n}+x\right)=a_{n+1}+f(x) \quad 1 \leq x \leq a_{n-1} \quad \text { in this case. }
$$

For this, we first note that the value of $f(y)$ is $y$ plus the number of "g" values between 1 and $f(y)$. This value is equal to the maximum $m$ such that $g(m)=f(f(m))+1 \leq f(y)$, which holds precisely when $f(m)a_{n}+x$, so $a_{n-1}1$ and $\alpha^{2}>1$. Furthermore, $1 / \alpha+1 / \alpha^{2}=1, \alpha$ and $\alpha^{2}$ are irrational, and thus the value sets of $f$ and $g$ each contain every integer exactly once (see Skljarskij-Chencov-Jaglom: Selected Problems and Theorems in Elementary Mathematics, Volume 1, Problem 108). Therefore, we only need to prove the

$$
g(n)=f(f(n))+1
$$

relationship. But $g(n) \neq f(n)$, since the value sets of $f$ and $g$ have no common elements. Furthermore, $[\alpha n]1$ and $1=\alpha^{2}-\alpha$ imply the inequality $\alpha n<\alpha+[\alpha n]=\alpha+\left(\alpha^{2}-\alpha\right)[\alpha n]$. Dividing this inequality by $\alpha$ and rearranging,

$$
n+[\alpha n]<\alpha[\alpha n]+1,
$$

from which

$$
\begin{aligned}
g(n) & =\left[\alpha^{2} n\right]=[(1+\alpha) n]= \\
=n+[\alpha n] & \leq[\alpha[\alpha n]+1]=f(f(n))+1 .
\end{aligned}
$$