5
$\begingroup$

If $f$ is a strictly increasing function from the naturals to the naturals, and $f(f(x))=3x$, what are all values of $f(2012)$? I have only proven that $f(3x)=3f(x)$ but that get's nowhere :(

  • 2
    I suggest that you start by looking at $f(x)$ for small values of $x$; look for a pattern when $x$ is written in base 3.2012-07-23

1 Answers 1

7

Proposition. $f(1) = 2$, $f(2) = 3$.

Proof. $f(1)$ cannot be $1$ otherwise we would have $ 3 = f(f(1)) = f(1) = 1 $ So $f(1) > 1$ and since $f$ is strictly increasing, $f(x) > x$ for each $x$.
Being $3 = f(f(1)) > f(1)$, the only remaining possibility is $f(1) = 2$.
Finally, $f(2) = f(f(1)) = 3$. $\blacksquare$

Proposition. $f(3^n x) = 3^n f(x)$.

Proof. This is a direct consequence of the relation $ f(3x) = f(f(f(x))) = 3f(x)\; \blacksquare $

Proposition. If $3^n < x \leq 2\cdot 3^n$ then $f(x) = 3^n + x$.

Proof. It's sufficient to note that there are exactly $3^n$ numbers between $3^n$ and $2\cdot 3^n$, and exactly $3^n$ numbers between $ f(3^n) = 3^nf(1)= 2\cdot 3^n $ and $ f(2\cdot 3^n) = 3^nf(2) = 3^{n +1} \; \blacksquare $

Proposition. If $2\cdot 3^n < x \leq 3^{n + 1}$ then $f(x) = 3x - 3^{n + 1}$.

Proof. Since $3^n < x - 3^n \leq 2\cdot 3^n$, the previous proposition implies $f(x -3^n) = x$ and therefore $ f(x) = f(f(x - 3^n)) = 3x - 3^{n + 1} \; \blacksquare $

Being $2\cdot 3^6 < 2012 \leq 3^7$, from last proposition we can conclude $ f(2012) = 3\cdot 2012 - 3^7 = 3849 $