Maths Olympiad Prep

Library / /62 of 133

Algebra Difficulty 5.5 AIME, harder Prove it Saudi Arabia

Let f:NNf: \mathbb{N} \rightarrow \mathbb{N} be a strictly increasing function such that f(f(n))=3nf(f(n))=3 n, for all nNn \in \mathbb{N}. Find f(2010)f(2010).
(Note: N={0,1,2,}\mathbb{N}=\{0,1,2, \ldots\} ).

Solutions — 2

Solution 1

It follows f(f(f(n)))=f(3n)f(f(f(n)))=f(3 n), hence for all nNn \in \mathbb{N} we have
f(3n)=3f(n)(1) f(3 n)=3 f(n) \tag{1}
For n=0n=0 we find f(0)=0f(0)=0. We have f(1)1f(1) \neq 1. Indeed, if f(1)=1f(1)=1, then we get 3=f(f(1))=f(1)=13=f(f(1))=f(1)=1, not possible. Hence f(1)>1f(1)>1, so 3=f(f(1))>f(1)>13=f(f(1))>f(1)>1. It follows f(1)=2f(1)=2, and consequently f(2)=f(f(1))=3f(2)=f(f(1))=3.
Now we prove by induction that for all nNn \in \mathbb{N}, we have
f(3n)=23n and f(23n)=3n+1(2) f\left(3^{n}\right)=2 \cdot 3^{n} \text{ and } f\left(2 \cdot 3^{n}\right)=3^{n+1} \tag{2}
Indeed, the relations (2) hold for n=0n=0. If they hold for a positive integer nn, then we get
f(3n+1)=f(33n)=3f(3n)=23n+1 f\left(3^{n+1}\right)=f\left(3 \cdot 3^{n}\right)=3 f\left(3^{n}\right)=2 \cdot 3^{n+1}
and
f(23n+1)=3f(23n)=3n+1 f\left(2 \cdot 3^{n+1}\right)=3 f\left(2 \cdot 3^{n}\right)=3^{n+1}
There are exactly 3n13^{n}-1 positive integers kk such that 3n<k<23n3^{n}<k< 2 \cdot 3^{n}. Also, there are exactly 3n13^{n}-1 positive integers kk' such that
f(3n)=23n<k<3n+1=f(23n) f\left(3^{n}\right)=2 \cdot 3^{n}<k'<3^{n+1}=f\left(2 \cdot 3^{n}\right)
The function ff is strictly increasing, then we have
f(3n+k)=23n+k,0k3n f\left(3^{n}+k\right)=2 \cdot 3^{n}+k, \quad 0 \leq k \leq 3^{n}
hence f(23n+k)=f(f(3n+k))=3(3n+k)f\left(2 \cdot 3^{n}+k\right)=f\left(f\left(3^{n}+k\right)\right)=3\left(3^{n}+k\right).
In our case, we have 2010=36702010=3 \cdot 670 and it follows
f(2010)=3f(670)=3f(235+184)=9(35+184)=3843. f(2010)=3 f(670)=3 f\left(2 \cdot 3^{5}+184\right)=9\left(3^{5}+184\right)=3843 .

Solution 2

Let n=a1a2atn=\overline{a_{1} a_{2} \ldots a_{t}} the representation of nn in base 3. We have, if a1=1a_{1}=1, then f(n)=2a2atf(n)=\overline{2 a_{2} \ldots a_{t}}. If a1=2a_{1}=2, then f(n)=1a2a3at0f(n)= \overline{1 a_{2} a_{3} \ldots a_{t} 0}. These relations are direct consequences from (2). As in the previous solution we have f(2010)=3f(670)f(2010)=3 f(670). But 670=220211670=220211, hence
f(670)=f(2202113)=12021103=36+235+233+32+3=1281, \begin{gathered} f(670)=f\left(220211_{3}\right)=1202110_{3} \\ =3^{6}+2 \cdot 3^{5}+2 \cdot 3^{3}+3^{2}+3=1281, \end{gathered}
and we get f(2010)=31281=3843f(2010)=3 \cdot 1281=3843.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.