Means and Set of Rational Numbers

Question

Let $S$ be the set $\{0, 1\}$. Given any subset of $S$ we may add its arithmetic mean to $S$ (provided it is not already included - $S$ never includes duplicates). Show that by repeating this process we can include the number $1/5$ in $S$. Show that we can eventually include any rational number between $0$ and $1$.

Answer 1

This is actually a cool question! OP should definitely detail what they've already tried though.

Lemma

If we can make $x$ and $y$ then we can make $x+\frac{k}{2^n}(y-x)$ for all $k\leq 2^n$.

Proof: for $n=1$, this is clearly true. Suppose it is true for $n=t$. Then for $n=t+1$, note that if $k$ is even then it reduces to the case for $t$, otherwise $$x+\frac{k}{2^{t+1}}(y-x)=\cfrac{1}{2}\left(\left(x+\frac{\frac{1}{2}(k-1)}{2^t}(y-x)\right)+\left(x+\frac{\frac{1}{2}(k+1)}{2^t}(y-x)\right)\right)$$ so by induction the lemma is true.

Lemma

If we can make $x$ and $y$ then we can make $x+(y-x)\frac{1}{n}$.

Proof: let $f(t)=x+t(y-x)$. Consider $f(\frac{1}{2}),f(\frac{1}{4}),\ldots,f(\frac{1}{2^{n-3}}),f(\frac{1}{2^{n-2}})$ (all makeable by lemma $1$) and add two "weird" terms $f(\frac{1}{2^{n}}),f(\frac{3}{2^{n}})$. Note that there are $n$ terms here, so the sum is $nx+(y-x)$ and thus their average is $x+\frac{1}{n}(y-x)$

Finally, to make $\frac{a}{b}$ we iterate lemma 2:

We can make $\frac{1}{b},\frac{2}{b},\frac{3}{b},\ldots,\frac{a}{b}$ by repeated using lemma 2 with $n=b,b-1,b-2,\ldots$.

And just for fun, an explicit construction for $\frac{1}{5}$:

$$0,1,\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{32}$$

are all quite easy to make; each is the average of the last one and $0$. Now $\frac{3}{32}$ is the average of $\frac{1}{8},\frac{1}{16}$. Finally, $$1=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{32}+\frac{3}{32}$$ so if you take their average you get $\frac{1}{5}$.