Hint for a

Click to reveal hidden text

very nice solution for b

Click to reveal hidden text

Hint for c

Click to reveal hidden text

Official Solution: For part (a) we use induction. If $bc-ad=1$ then $b(a+c)-a(b+d)=ba+bc-ab-ad=bc-ad=1$ and $(b+d)c-(a+d)c=bc+dc-ad-dc=bc-ad=1$ which proves the induction step. It is obvious that it is true at the beginning of the process. Now if $bc-ad=1$ then $(a,b)=1$. So every fraction appearing in this process is simplified. We will show that if $x$ is a number generated in one of the processes, then $\frac 1x,x+1,x-1$ are also produced. For the first operation: If the $i^{th}$ number, counting from the beginning of the sequence, is $\frac ab$, then the $i^{th}$ number, counting from the end of the sequence, would be $\frac ba$. This is true at the beginning. ($\frac 10,\frac 01$) And using induction, it is no hard to prove it. Now note that the sequence generated by $a+1,b+1$ as the first and the last fraction is exactly the sequence generated by $a,b$ as the first and the last fraction, plus $1$. (that is a $1$ is added to each term of the sequence) Again this is easy to prove using induction. At the beginning it is true. If $\frac ab,\frac cd$ are generated somewhere in the second sequence, then $\frac {a+b}b,\frac {c+d}d$ are generated in the first sequence. The next fraction appearing between them is $\frac{a+c+b+d}{c+d}$ which is one unit more than $\frac{a+c}{b+d}$ (the one appearing in the second sequence) Now note that, in the $1^{st}$ step of the process, the number appearing just before $\frac 10$ is $\frac 11$. Therefor the numbers appearing between $\frac 11,\frac 10$ are exactly one unit more than the numbers appearing between $\frac 01,\frac 10$. (which are all the numbers appearing in the process) So if $x$ appears in the process, $x+1$ does, and if $x+1$ does, then so does $x$. Now for the second process: It is obvious that if $x$ appears, then so does $x+1$, because the first circles are one unit apart from each other. A unit inversion from the $0$ of the x axis, maps circles to circles, and tangent ones to tangent ones. The circle above $0$ is mapped to the line $y=1$. So the circles tangent to it, are mapped to the circles tangent to $y=0$ and $y=1$. Each two consecutive circles among these ones are mapped to tangent circles. Therefor these circles are mapped to circles above natural numbers, with diameter $1$. (the first circles of the process) Since the inverse of inversion is itself, the circles above natural numbers are mapped to circles appearing in the process and tangent to the circle above $0$. This inversion maps the point $x$ of the real line to $\frac 1x$. Therefor if $x$ appears in the process, $\frac 1x$ appears in the image of the process under the inversion which also appears in the first sequence itself. So in both processes, if $x$ appears, then so does $\frac 1x$ and $x+1$ and $x-1$. (if it's not negative) Now consider the Euclidean algorithm for a pair of relatively prime numbers $(a,b)$. In each step if our pair is $(a,b)$ consider the fraction $\frac ab$. Then a step consisting of swapping the numbers is the same as replacing our fraction $x$ by $\frac 1x$. A step consisting of replacing $(a,b)$ by $(a-b,b)$ is the same as replacing $x$ by $x-1$. Therefor after some number of moves of the form $x\rightarrow\frac 1x$ and $x\rightarrow x-1$, $x$ becomes $\frac 01$. (because $(a,b)$ were relatively prime) Using the inverse operations, which are $x\rightarrow\frac 1x$ and $x\rightarrow x+1$, we see that we can reach each rational number from $\frac 01$ which is present in both processes. So all the rational numbers appear in both processes. What remains to prove, is to show that only rational numbers appear in the second process. But it is a straightforward induction. Assume that two tangent circles $C_1,C_2$ appeared in the process and we know that their tangency points with the x axis are rational numbers. Using some unit translations and inversion from $0$, we can map $C_1$ to the circle above $0$. We have already shown that these operations and their inverse maps, map circles appearing in the process to circles appearing in the process. So now we have two circles appearing in the process, and one of them is the one above $0$. We know that the circles tangent to this one are the circles above $\frac 1n$'s. So the circle between $C_1,C_2$ is mapped to a circle above $\frac 1n$ for some $n$ which has a rational tangency point. Since our operations map rational numbers to rational numbers, the original tangency point should have been a rational number; which completes the proof.

Farey sequences; https://www.youtube.com/watch?v=0hlvhQZIOQw&ab_channel=Numberphile