Brazilian Math Olympiad

First note that if $n$ is written in the Fibonacci basis (as a sum of distinct Fibonacci numbers containing no neighbors), then the representation of $f(n)$ is just that of $n$ with a 0 in the end. The proof goes by induction: it is true for $n=0$. Suppose $n > 0$. Then $r$ will be such that $f(r) = n$, if the last digit of the Fibonacci of $n$ is zero, or $f(r) = n-1$, if it is one. Then $f(n) = n+r+n-f(r)$. If the last digit of the Fibonacci of $n$ is zero, then $r$ is obtained by deleting the last digit from $n$. So $f(n) = n+r$ is the sum of the Fibonacci numbers used in the representation of $n$ and its respective antecessors in the Fibonacci sequence, resulting in the subsequent Fibonacci numbers, which is exactly $n$ with a zero at its right. If the last digit of the Fibonacci of $n$ is zero, then $r$ is still obtained by deleting the last digit from $n$, but $f(n) = n+1+r$. Note that $n-1$ ends with a zero, so summing $r$ will do the same thing as the preceding case; and we're substituting the rightmost digit one with 2, which corresponds to a rightmost 10.

Now, express $n$ and $f(n)$ by using the closed form for Fibonacci numbers $F_k = \frac{1}{\sqrt{5}}(\phi^k - (-\phi)^{-k})$, and note that we cannot use two consecutive Fibonacci numbers in base Fibonacci, so $|f(n) - \phi \cdot nZ| < \phi^{-1}(1 + \phi^{-2} + \phi^{-4} + \dots) = \frac{\phi^{-1}}{1-\phi^{-2}} = 1$, that is, $f(n) - 1 < \phi n < f(n) + 1$. Thus if $m \le \phi n$ then $m < f(n) + 1 \iff m \le f(n)$ and the match is tough; if $m \ge \phi n + 1$ then $m > f(n) - 1 + 1 = f(n)$ and the match is not tough.