If $f:\mathbb N\to\mathbb N$ such that $f\big(f(x)\big)=3x$, then find $f(2013)$. If $f:\mathbb N\to\mathbb N$ such that $f\big(f(x)\big)=3x$, then what is the value of $f(2013)$?
 A: We can probably assume that $f$ is a strictly increasing function.
We know $f(f(1))=3$ so what is then $f(1)$? It can't be $3$ and can't be $1$, so we must have $f(1)=2$ and $f(2)=3$. We also need $6=f(f(2))=f(3)$, so $f(3)=6$. And so on. $9=f(f(3))=f(6)$, $18=f(9)$, $54=f(18)$...
From $f(3)=6$ and $f(6)=9$ we can derive that $f(4)=7$ and $f(5)=8$.
From that $f(7)=12$ and $f(8)=15$.
From that $f(12)=21$ and we know $18=f(9)<f(10)<f(11)<f(12)=21$ so we know that $f(10)=19$ and $f(11)=20$.
You can probably work your way up.
We also know $2013=3\cdot11\cdot61$ so we need $2013=f(f(11\cdot61))$ and so $f(2013)=3f(11\cdot61)$
But I expect there is an easier solution :)
A: We can define two functions $g$ and $h$ this way:
$$g(0)=h(0)=0$$
$$g(3k)=3g(k)$$
$$g(3k+1)=3k+2$$
$$g(3k+2)=9k+3$$
$$h(3k)=3h(k)$$
$$h(3k+1)=9k+6$$
$$h(3k+2)=3k+1$$
You can easily check that $g$ and $h$ satisfy the condition of the problem, and that $g(2013)=6030$ and that $h(2013)=2010$, so we can't guess the value of $f(2013)$ with that only condition.
This idea can be generalized:
Let $A$ be the set of natural numbers that are not multiple of $3$. Let $\{B,C\}$ any partition of $A$ (that is, $B\cup C=A$ and $B\cap C=\emptyset)$ with the only condition of that both sets are infinite. Take for example: squares and not squares, primes and not primes, etc. Since $B$ and $C$ are infinite and countable there is a bijection $\sigma$ from $B$ to $C$. In fact there are infinitely many of such bijections.
Now define: $f(0)=0$, $f(3k)=3f(k)$, $f(k)=\sigma(k)$ if $k\in B$ and $f(k)=3\sigma^{-1}(k)$ if $k\in C$. Let's prove that $f(f(x))=3x$ for all $x$ by induction. This is clearly satisfied for $x=0$.  
Then, for each $x>0$ we have three possibilities: 


*

*if $x$ is a multiple of $3$, then $x=3k$, so $f(f(x))=f(f(3k))=f(3f(k))=3f(f(k))=3\cdot3k=3x$ by the induction hypothesis. Note that $k<x$.

*if $x\in B$, then $f(f(x))=f(\sigma(x))=3\sigma^{-1}(\sigma(x))=3x$

*if $x\in C$, then $f(f(x))=f(3\sigma^{-1}(x))=3f(\sigma^{-1}(x))=3\sigma(\sigma^{-1}(x))=3x$


c.q.d.
It is clear that the concrete value of $f(2013)$ strongly depends on the chosen partition and on the chosen bijection for that partition.
In fact, I suspect that $f(2013)$ can be any multiple of $3$.
