Let $S$ be a set of rational numbers with the following properties: (a) $\frac12$ is an element in $S$, (b) if $x$ is in $S$, then both $\frac{1}{x+1}$ and $\frac{x}{x+1}$ are in $S$. Prove that $S$ contains all rational numbers in the interval $(0, 1)$.
Problem
Source: 2006 MOP Homework Blue NT 1
Tags: set, rational numbers, rational, number theory, strong induction
13.04.2020 00:34
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.
24.05.2020 16:25
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).
28.09.2020 02:45
This was also BMO 2004/5 Problem 5
04.11.2024 14:44
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)$.