Brazilian Mathematical Olympiad

The upper bound follows by induction. Let $S_m$ be the statement that $f(n) \le 5\log_3 n$ for $n \le 3m+2$. We have $2 = 1+1$, $3 = 1+1+1$, $4 = 1+1+1+1$, $5 = 1+1+1+1+1$, so $f(2) = 2$, $f(3) = 3$, $f(4) = 4$, $f(5) = 5$. We have $1 = \log_3 3 < \log_3 4 < \log_3 5$, so $f(3) < 5\log_3 3$, $f(4) < 5\log_3 4$ and $f(5) < 5\log_3 5$. Also $2^4 = 16 > 3^2$, so $2 < \log_3 2^4 = 4\log_3 2$. Hence $5\log_3 2 > 4\log_3 2 > 2 = f(2)$. So $S_1$ is true. Suppose $S_m$ is true. We have $3m+3 = (1+1+1) \times (m+1)$, so $f(3m+3) \le 3+f(m+1) = 3+5\log_3(m+1) < 5(1+\log_3(m+1)) = 5\log_3(3m+3)$. Similarly, since $3m+4 = 1+(3m+3)$, we have $f(3m+4) \le 4+f(m+1) < 5\log_3(3m+3) < 5\log_3(3m+4)$. Similarly, $f(3m+5) \le 5+f(m+1) \le 5+5\log_3(m+1) = 5\log_3(3m+3) < 5\log_3(3m+5)$. So $S_{m+1}$ is true. So $S_m$ is true for all $m$.

Induction also works for the lower bound. In any expression for $n$ using $1$s we either have $n = a + b$, with further expressions for $a$ and $b$, or we have $n = a \cdot b$ with further expressions for $a$ and $b$. In the first case if $a = 1$, we have to show that $1 + \log_3 b \ge \log_3(b+1)$, but that is almost obvious since $1 + \log_3 b = \log_3(3b) > \log_3(b+1)$. If $a, b > 1$, then we have to show that $\log_3 a + \log_3 b \ge \log_3(a+b)$, which is again obvious, since if $a \ge b \ge 2$ we have $\log_3 a + \log_3 b = \log_3(ab) \ge \log_3(2a) \ge \log_3(a+b)$. In the second case we can assume that $a, b > 1$ (since there is no benefit in the expression if $a = 1$ or $b = 1$), so we have to show that $\log_3 a + \log_3 b \ge \log_3(ab)$ which is true (we have equality). So all we need are the starting cases. For $n = 2$, it is clear that $f(2) = 2$, but $8 < 9$, so $\log_3 8 < \log_3 9$ or $3\log_3 2 < 2 = f(2)$, as required.