3 Let $f(n)$ be a function satisfying the following three conditions for all positive integers $n$ :
(a) $f(n)$ is a positive integer,
(b) $f(n+1)>f(n)$,
(c) $f(f(n))=3 n$.
Find $f$ (2001).
We will present two solutions. The first one was presented by the problem proposer, and was the method used essentially by all the students but one. The second solution, which won the BAMO 2001 Brilliancy Prize, is due to Andrew Dudzik of Lynbrook HS. Andrew's solution, (which we only sketch) is not shorter, nor does it use any ingenious mathematical tricks. But it is superior to the other solutions, because it illuminates the nature of $f(n)$ in a very simple way.
Solution 1: We will show that $f(2001)$ must equal 3816 . We start by proving a lemma which gives us some of the values of $f(n)$.
Lemma: For $n=0,1,2, \ldots$,
(a) $f\left(3^{n}\right)=2 \cdot 3^{n}$; and
(b) $f\left(2 \cdot 3^{n}\right)=3^{n+1}$.

Proof: We use induction. For $n=0$, note that $f(1) \neq 1$, otherwise $3=f(f(1))=f(1)=1$, which is impossible. Since $f(k)$ is a positive integer for all positive integers $k$, we conclude that $f(1)>1$. Since $f(n+1)>f(n), f$ is increasing. Thus $1<f(1)<f(f(1))=3$ or $f(1)=2$. Hence $f(2)=f(f(1))=3$.
Suppose that for some positive integer $n \geq 1$,
$$
f\left(3^{n}\right)=2 \cdot 3^{n} \text { and } f\left(2 \cdot 3^{n}\right)=3^{n+1} \text {. }
$$

Then,
$$
f\left(3^{n+1}\right)=f\left(f\left(2 \cdot 3^{n}\right)\right)=2 \cdot 3^{n+1}
$$
and
$$
f\left(2 \cdot 3^{n+1}\right)=f\left(f\left(3^{n+1}\right)\right)=3^{n+2},
$$
as desired. This completes the induction, and establishes the lemma.
Continuing with our solution, there are $3^{n}-1$ integers $m$ such that $3^{n}<m<2 \cdot 3^{n}$ and there are $3^{n}-1$ integers $m^{\prime}$ such that
$$
f\left(3^{n}\right)=2 \cdot 3^{n}<m^{\prime}<3^{n+1}=f\left(2 \cdot 3^{n}\right) .
$$

Since $f$ is an increasing function,
$$
f\left(3^{n}+m\right)=2 \cdot 3^{n}+m
$$
for $0 \leq m \leq 3^{n}$. Therefore
$$
f\left(2 \cdot 3^{n}+m\right)=f\left(f\left(3^{n}+m\right)\right)=3\left(3^{n}+m\right)
$$
for $0 \leq m \leq 3^{n}$. Hence
$$
f(2001)=f\left(2 \cdot 3^{6}+543\right)=3\left(3^{6}+543\right)=3816 .
$$

Solution 2: (Sketch) Andrew Dudzik's insight was to recognize that $f(n)$ deals in a very simple way, with the base- 3 representation of $n$. Let $n=a_{1} a_{n} \cdots a_{t}$ be the base- 3 digits of $n$. For example, if $n=50$ in base 10, we would write $n=1212$ in base 3 and hence $a_{1}=1, a_{2}=2, a_{3}=1, a_{4}=2$. Dudzik proved the following:
1. If $a_{1}=1$, then $f(n)=2 a_{2} a_{3} \cdots a_{t}$.
2. If $a_{1}=2$, then $f(n)=1 a_{2} a_{3} \cdots a_{t} 0$

These two statements can be proven easily with induction; we leave this an an exercise for the reader. Note that Dudzik's formulas allow us to immediately compute $f$ (2001). In base-3 notation, 2001 is equal to 2202010. Thus, by formula \#2,
$$
f(2202101)=12020100=1 \cdot 3^{2}+2 \cdot 3^{4}+2 \cdot 3^{6}+3^{7},
$$
and this equals 3816 in base-10 notation.