The set $T$ contains some real numbers, according to the following three rules:
- $1/1$ is in $T$
- If $\dfrac{a}{b}$ is in $T$ (where $a/b$ is irreducible) then $\dfrac{b}{2a}$ is in $T$
- if $\dfrac{a}{b}$ and $\dfrac{c}{d}$ are in $T$ and both irreducible then $\dfrac{a+c}{b+d}$ is also in $T$.
Describe which numbers are in $T$.
I initially tried looking at small cases(I.e taking $1/1$, applying ii to it to get $1/2$, then using both operations again and so on. However I couldn’t find any patterns to prove so I guess my approach will have to change. Please help somebody! I spent ages on it. Also it’s from a practice USAMO paper.
I claim that that answer is any fraction strictly between 0 and 1, here is a proof by construction.
For any fraction $ \frac{a}{b} $ where $ a < b $, if we could construct $ \frac{1}{b - a + 1} $, then we can construct $ \frac{a}{b} = \frac{1 + \cdots + 1}{b - a + 1 + \cdots 1} $. Therefore the key is to construct $ \frac{1}{x} $ for $ x > 0 $.
Here is the key idea, we can construct $ \frac{1}{x} $ with one binary digit at a time. We start with $ \frac{1}{1} $ and then add a binary digit to the end of the denominator one at a time.
It is easy to add a zero, just apply the divide by 2 rule.
To add a one, we first add a zero, and then we add $ \frac{1}{1} $, that add a 1 to the denominator, with a side effect that the numerator become 2, we can easily get rid of that by dividing it by 2.
So that's it, we can construct any number we want. As an example, let's construct $ \frac{5}{12} $.
$ \frac{5}{11} = \frac{1 + 1 + 1 + 1 + 1}{6 + 1 + 1 + 1 + 1} $, therefore, if we could construct $ \frac{1}{6} $, we are done.
To construct $ \frac{1}{6} $, we proceed as follow $ \frac{1}{1} \to \frac{1}{2} \to \frac{2}{3} \to \frac{1}{3} \to \frac{1}{6} $