What value will take $f(100)$?

Let $f$ be a function from the positive integers into the positive integers and which satisfies $f(n + 1) > f(n)$ and $f(f(n)) = (f \circ f) (n) = 3n$ for all $n$. Find $f(100)$.

This is one of the questions we presented in one session to contest preparation PUTNAM. It turns out that I can't get from the problem. Could someone just give me a hint?

The function is clearly increasing, so $f(99)<f(100)<f(102)$. Since $f(99)=f(f(f(f(f(11)))))$, it makes sense that we'd want to know $f(11)$. Also, $f(102)=f(f(f(34)))$, so we want $f(34)$. After a while, one arrives at the following solution:

$f(1)\ne1$, since $f(1)=1$ implies $3=f(f(1))=f(1)=1$. Thus, $1<f(1)$. Since the function is increasing, we have $f(1)<f(f(1))=3$. Thus, $1<f(1)<3$, and $f(1)=2$.

$f(2)=f(f(1))=3$, and $f(3)=f(f(2))=6$. $f(6)=f(f(3))=9$. Since the function is increasing, this implies $f(4)=7$ and $f(5)=8$.

$f(7)=f(f(4))=12$. $f(9)=f(f(6))=18$, and $f(12)=f(f(7))=21$. Again, due to the increasing nature of $f$, we have $f(10)=19$ and $f(11)=20$.

$f(21)=f(f(12))=36$. $f(33)=f(f(20))=60$, and $f(36)=f(f(12))=63$. Thus, due to $f$ being increasing, $f(34)=61$ and $f(35)=62$. $f(60)=f(f(33))=99$, and $f(61)=f(f(34))=102$.

$f(99)=f(f(60))=180$ and $f(102)=f(f(61))=183$. Since $f$ is increasing, $f(100)=181$ and $f(101)=182$.

Thus: $$f(100)=181$$

In general:

• If the base 3 representation of $n$ starts with a $1$, $f(n)$ switches it to $2$;

• If the base 3 representation of $n$ starts with a $2$, $f(n)$ switches it to $1$ and multiplies by $3$.

Given this, we simply write $100 = 81 + 9 + 9 + 1 = 10201_3$, so that $$ f(100) = f(10201_3) = 20201_3 = \boxed{181}. $$

Proof of this description of $\boldsymbol{f}$

It is clear that $f$, when defined this way, satisfies $f(n+1) > f(n)$ and $f(f(n)) = 3n$ for all $n$. So if you are assuming $f(100)$ is completely determined by these conditions (given the wording of the problem), you can stop here.

Otherwise, we need to prove that the $f$ we defined is the only possible $f$. So fix any $g$ satisfying $g(g(n)) = 3n$ and $g(n+1) > g(n)$ for all $n$; we will prove that $g(n) = f(n)$ for all $n$, where $f(n)$ is as we defined.

First, note the following: (1) $g$ is surjective onto multiples of three (since $g(g(n)) = 3n$); (2) $g(3n) = g(g(g(n))) = 3g(n)$; (3) $f$ is surjective onto multiples of three; (4) $f(3n) = 3f(n)$; and (5) $f(n+1) - f(n) \in \{1, 3\}$ for all $n \ge 1$. (3) and (4) are justified by the same reasoning as (1) and (2); (5) is the most important and follows from our definition of $f$, if you do cases on the base $3$ representation of $n$.

We proceed by strong induction. For the base case, as others have observed, $1 < g(1) < 3$ implies $g(1) = 2$ and $g(2) = 3$, i.e. $g(1_3) = 2_3$ and $g(2_3) = 10_3$, so $g$ agrees with $f$.

For the inductive step, fix $k \ge 1$, suppose that $g(i) = f(i)$ for $i \le k+1$, and consider $g(3k), g(3k+1), g(3k+2), g(3k+3)$. We have $g(3k) = 3g(k) = 3f(k)$, and $g(3k+3) = 3f(k+1)$. By (5), there are two cases:

• If $f(k+1) - f(k) = 1$, for $g$ to be strictly increasing we must pick $g(3k+1) = 3f(k) + 1$, and $g(3k+2) = 3f(k) + 2$. In particular $g(3k+1) = f(3k+1), g(3k+2) = f(3k+2)$.

• If on the other hand $f(k+1) - f(k) = 3$, for $g$ to be surjective onto multiples of $3$ we must pick $g(3k+1) = 3f(k) + 3$, $g(3k+2) = 3f(k) + 6$. In particular $g(3k+1) = f(3k+1), g(3k+2) = f(3k+2)$.

So this completes the induction.

As per Akiva Weinberger's comment, we have that $f(1) = 2, f(3) = 6$ and $f(6)=9$. As $f$ is increasing, this forces $f(4)=7$ and $f(5)=8$.

As $f(7)=f(f(4))=3\cdot4=12$, we have $f(12)=3\cdot7=21$. Similarly, $f(9)=f(f(6))=18$. So we have: $$f(9)=18<f(10)<f(11)<f(12)=21$$ giving $f(10)=19, f(11)=20$.

Then $f(20)=f(f(11))=33$ and $f(21)=f(f(12))=36$

So $$f(33)=f(f(20))=60<f(34)<f(35)<f(36)=f(f(21))=63$$ Which forces $f(34)=61$.

So, $f(60)=f(f(33))=99$ and $f(61)=f(f(34))=102$.

Finally, $$f(99)=f(f(60))=180<f(100)<f(101)<f(102)=f(f(61))=183$$ and so $$f(100) = 181$$

The main idea used in this solution is that if for some $k$, $f(k+1) = f(k)+1$, then $$f(3k)=f(f(f(k)))=3f(k)<f(3k+1)<f(3k+2)<f(3k+3)=f(f(f(k+1)))=3f(k+1) =3(f(k)+1) = 3f(k) +3$$ so $f(3k+1)=f(3k)+1$ and $f(3k+2)=f(3k)+2$. As a direct corollary, if we can apply this to $k$, we can also apply it to $k'=3k, 3k+1$ or $3k+2$.