Balkan Mathematical Olympiad Shortlist

The crucial observation that solves this problem is that the function $f$ encodes Euclid's algorithm when we view numbers in binary. To make this precise, we will write $g(n)$ for $f(n+1)$, and consider for each integer $n$ the pair $(f(n),g(n))$. If we let $x$ be the binary string representing $n$ then the recurrence relations give us that $$(f(x0),g(x0))=(f(x),f(x)+g(x))\text{ and }(f(x1),g(x1))=(f(x)+g(x),g(x)).$$ Thus we can calculate the pair $(f(x),g(x))$ as follows: start from the pair $(1,1)=(f(1),g(1))$. Now read the binary digits of $x$ from left to right, ignoring the initial 1: whenever you see a 0 add the first coordinate to the second, and whenever you see a 1 add the second coordinate to the first. For example, to calculate the pair $(f(27),g(27))$ we write $27=11011$ in binary, which gives us the sequence of pairs $$\begin{array}{rl}(f(1),g(1))& =(1,1)\\ (f(11),g(11))& =(2,1)\\ (f(110),g(110))& =(2,3)\\ (f(1101),g(1101))& =(5,3)\\ (f(11011),g(11011))& =(8,3)\end{array}$$ Now from this it follows by induction that $(f(n),g(n))$ are coprime positive integers, with $f(n)\ge g(n)$ if and only if $n$ is odd. To complete the proof, we just need to show that each pair $(a,b)$ of coprime positive integers arises as $(f(n),g(n))$ for a unique positive integer $n$.

To show existence of $n$, imagine running Euclid's algorithm on the pair $(a,b)$: that is to say, we successively either subtract the first coordinate from the second or the second from the first (depending on which of the two is the larger) until we can't go any further, which is when we reach the pair $(1,1)$. We can record this as a string consisting of a 0 for each time we subtracted the first from the second, and a 1 for each time we subtracted the second from the first. Reversing this string and prepending a 1 gives the binary expansion of a number $n$ which (by our method of calculating $(f,g)$) has $(f(n),g(n))=(a,b)$. To get uniqueness of $n$ we just have to note that when we ran Euclid's algorithm to construct $n$ in the previous paragraph, we had no choices at any stage: there is a unique series of reductions that takes $(a,b)$ to $(1,1)$ while remaining in positive integers. This series of reductions corresponds to a unique binary string, so the integer $n$ we constructed was unique.

---

Alternative solution.

As in the previous solution, we consider the pair $(f(n),f(n+1))$ for each positive integer $n$, show by induction that $(f(n),f(n+1))$ are coprime, and that $f(n)\ge f(n+1)$ if and only if $n$ is even. However, to show that each pair $(a,b)$ of coprime positive integers arises as $(f(n),f(n+1))$ for a unique $n$, we proceed by strong induction on $a+b$. Specifically, if $a<b$ then $(a,b-a)=(f(m),f(m+1))$ for some integer $m$, whence $(a,b)=(f(2m),f(2m+1))$ by the recursive rules for $f$. To show uniqueness, if $(a,b)=(f(n),f(n+1))$ then (since $a<b$) we know that $n=2k$ must be even. However, then by the recursive rules for $f$ again $(a,b-a)=(f(k),f(k+1))$ so that (inductive hypothesis) $k=m$. This gives uniqueness. The case $a>b$ is similar and the exceptional case $(a,b)=(1,1)$ is easy, which completes the proof.