My First International Competition!

Relevant wiki: Functional Equations - Problem Solving

We cannot have $f(1) = 1$ as this implies $f(f(1)) = 1$ . If $f(1) = 3$ then $f(f(1)) = 3 = f(3)$ , which is absurd since $f$ is strictly increasing therefore $f(1) \neq f(3)$ . Similar arguments force $f(1) = 2$ .

Therefore, $f(f(1)) = f(2) = 3 \implies f(f(2)) = f(3) = 6 \implies f(f(3)) = f(6) = 9$ .

Since $f(3) = 6$ and $f(6) = 9$ , this forces $f(4) = 7, f(5) = 8$ .

$f(6) = 9 \implies f(f(6)) = f(9) = 18 \implies f(f(9)) = f(18) = 27$ .

Similarly, $f(5) = 8 \implies f(f(5)) = f(8) = 15 \implies f(f(8)) = f(15) = 24$ .

Since $f(15) = 24$ and $f(18) = 27$ , this forces $f(16) = 25, f(17) = 26$ (Since $f$ is increasing).

Therefore, our answer is $\boxed{25}$

Relevant wiki: Induction - Functional Equations

We will prove via induction on all non-negative integers $n$ a claim $P_n$ that:

• For $3^n \leq x \leq 2 \cdot 3^n$ , we have $f(x)=x+3^n$
• For $2 \cdot 3^n \leq x \leq 3^{n+1}$ , we have $f(x)=3x-3^{n+1}$

First, we prove that $f(1)=2$ .

If $f(1)=1$ , we have $f(f(1))=1=3$ , a contradiction, hence $f(1)>1$ and with the condition $f(n+1)>f(n)$ , we have $f(n)>n$ for all positive integers $n$ .

If $f(1) \geq 3$ , we'd have $f(f(1)) \geq f(3) >3$ , also a contradiction. Hence we must have $f(1)=2$ . Also, we have $f(2)=f(f(1))=3$ and $f(3)=f(f(2))=6$ .

We note that we have our claim $P_n$ be true for $n=0$ , given our values of $f(1),f(2),f(3)$ . Now assume for some non-negative integer $k$ , we have $P_k$ be true, i.e. that:

• For $3^k \leq x \leq 2 \cdot 3^k$ , we have $f(x)=x+3^k$
• For $2 \cdot 3^k \leq x \leq 3^{k+1}$ , we have $f(x)=3x-3^{k+1}$

We then consider the claim $P_{k+1}$ :

For $3^{k+1} \leq x \leq 2 \cdot 3^{k+1}$ , consider the $x$ where $x=3y$ for some integer $3^k \leq y \leq 2 \cdot 3^k$ . We then have $x=f(f(y))=f(y+3^k)$ , and consequently $f(x)=f(f(y+3^k)))=3(y+3^k)=3y+3^{k+1}=x+3^{k+1}$ .

For $3^{k+1} \leq x \leq 2 \cdot 3^{k+1}$ , there also exist $x,x+1$ where $3y<x<x+1<3(y+1)$ for some $(3^k \leq y \leq 2 \cdot 3^k-1$ . We can infer that $x=3y+1,x+1=3y+2$ . Then using our results that $f(3y)=3y+3^{k+1},f(3y+3)=3y+3+3^{k+1}$ from just now, we have:

$3y+3^{k+1}=f(3y)<f(x)<f(x+1)<f(3y+3)=3y+3+3^{k+1}$ We thus have $f(x)=3y+1+3^{k+1}=x+3^{k+1},f(x+1)=3y+2+3^{k+1}=x+1+3^{k+1}$ , hence we have it that for all $3^{k+1} \leq x \leq 2 \cdot 3^{k+1}$ , we have $f(x)=x+3^{k+1}$

For $2 \cdot 3^{k+1} \leq x \leq 3^{k+2}$ , we note that $3^{k+1} \leq x-3^{k+1} \leq 2 \cdot 3^{k+1}$ and from our previous result we have $f(x-3^{k+1})=x-3^{k+1}+3^{k+1}=x$ . Consequently, we have $f(x)=f(f(x-3^{k+1}))=3x-3^{k+2}$ .

Thus we have proven that with $P_0$ being true and $P_k$ being true $\Rightarrow$ $P_{k+1}$ being true, we have proven our claim that $P_n$ is true for all non-negative integers n.

Given that $3^2 \leq 16 \leq 2 \cdot 3^2$ , we apply our formula to get $f(16)=25$ .

The given equation yields :

$∀n∈ℕ, f(f(f(n))) = \begin{cases} f^2(f(n)) = 3f(n) \\ f(f^2(n)) = f(3n)\end{cases}$

Thus :

$∀n∈ℕ, f(3n) = 3f(n)$

Hence, by induction :

$∀m,n∈ℕ, f(3^nm) = 3^nf(m)$

But it also known for sure that

$∀n∈ℕ, 0 < f(n) < f(f(n)) = 3n$

Therefore :

$0 < f(1) < 3$

And as $f(1) ≠ 1$ (otherwise $3 × 1 = f(f(1)) = f(1) = 1$ ) :

$f(1) = 2$

Therefore :

$\begin{cases} f(2) = f(f(1)) = 3 × 1 \\ f(3) = 3 × f(1) = 6 ⟹ f(5) > f(4) > f(3) = 6 ⟹ f(5) ≥ 8 \end{cases}$

$24 = 3 × 8 ≤ 3 f(5) = f(15) < f(16) < f(17) < f(18) = 9 f(2) = 9 × 3 = 27$

Hence :

$f(16) = 25$