Note that $1/2\in S$, and $1/2/(1/2+1)=1/3\in S$ as well. Furthermore, note that $1/(1/2+1)=2/3\in S$. We now prove by (strongly) inducting on $\ell$ that for every $\ell\geqslant 2$, $k/\ell \in S$, where $1\leqslant k\leqslant \ell-1$, and $(k,\ell)=1$. Note that the base cases $\ell=2,3$ are already established above. Suppose the assertion holds for every positive integer up to $\ell-1$. Let $k\in[1,\ell-1]\cap \mathbb{Z}$ with $(k,\ell)=1$. Suppose $\ell-k<k$. Then, $\frac{1}{\frac{\ell-k}{k}+1} = \frac{k}{\ell}\in S$, as requested. Suppose now $\ell-k>k$. Then $\frac{\frac{k}{\ell-k}}{1+\frac{k}{\ell-k}}= \frac{k}{\ell}\in S$ (note that in both cases above, I've used the facts that $(k,\ell)=(\ell-k,k)=1$, and inductive hypotheses applied on $k$ and $\ell-k$, respectively). This finishes the conclusion.

Essentially the process sends (a,b) to (a, a+b) and (b, a+b). In other words, this problem wants us to show that when there are two coprimes numbers, using Euclidean algorithm to arrive at their gcd always lands us at (1,2). This is true because every time the Euclidean algorithm is used, we arrive at a lower sum and so (1,1) is our final destination, and right before this should always come (1,2).

This was also BMO 2004/5 Problem 5

We induct strongly. Note that $S$ has all fractions in $(0, 1)$ with denominator $2$. Assume that at some point, $S$ has all fractions of the form $\frac ab$ with $a < b < n$. We show that we can get all fractions of the form $\frac an$ such that $a < n$. Note that $\frac an \in S \impliedby \frac{n-a}{a} \in S$, as $$\frac{1}{\frac{n-a}{a} + 1} = \frac an.$$But at the same time, the denominator of $\frac{n-a}{a}$ is $a < n$ by assumption, so $\frac{n-a}{a} \in S$. This suffices to show that any rational number in $(0, 1)$ with denominator $n$ exists, for all $n \in \mathbb{N}$; in other words, $S$ contains all rationals in $(0, 1)$.