A set contains $0$, $1$, and all averages of any subset of its element, prove it contains all rational number between 0 and 1

Solution 1:

Assume there is some $\frac ab\notin A$ (with $0\le a\le b$) and among all such counterexamples consider one with minimal denominator $b$ (especially, $\frac ab$ is in shortest termes). Then certainly $b>1$. If $b$ is a power of $2$, note that $a$ is odd and $\frac ab=\frac12\left(\frac{(a-1)/2}{b/2}+\frac{(a+1)/2}{b/2}\right)\in A$, contradiction. Thus let $p$ be an odd prime dividing $b$, $b=pc$. Then by minimality of $b$, all fractions $\in[0,1]$ with denominator dividing $c$ are $\in A$. Also all fractions with denominator dividing $2^kc$ for some $k\in \Bbb N_0$ are $\in A$ (by induction as above: $\frac xy$ with $x$ odd is the average of $\frac{(x-1)/2}{y/2}$ and $\frac{(x+1)/2}{y/2}$). Let $\hat c=2^kc$ and $\hat b=p\hat c=2^kb$ where $k$ is chosen large enough so that $$\tag1 \hat c>6p-12$$ or, as a consequence of $(1)$ $$\tag2 \hat b+2\ge 3{p-1\choose 2}. $$ For $0\le x\le b$ we might try to write $\frac x{\hat b}$ as average of $p$ fractions with denominator (a divisor of) $\hat c$. For this we should find $p$ numbers $x_i$, $i=1,\ldots,p$, with $0\le x_1<x_2<\ldots<x_p\le c$ and $x_1+\ldots+x_p=x$. This would give us $\frac xb=\frac1p\left(\frac{x_1}c+\ldots+\frac{x_p}c\right)\in A$ as desired. However, the smallest possible pick for $x_1+\ldots +x_p$ is $0+1+2+\ldots +(p-1)={p-1\choose 2}$ and the largest is $p\hat c-{p-1\choose 2}$ (and all this is possible in the first place because $(1)$ guarantees $\hat c\ge p-1$); but at least we can obtain all intermediate integers as sum, as we can always "step up" by increasing $x_p$ if it is $< c$ or any of the other $x_i$ that is $<x_{i+1}-1$! We thus conclude that $\frac x{\hat b}\in A$ for ${p-1\choose 2}\le x\le b-{p-1\choose 2}$. Assume there exists $x$ with $0<x<{p-1\choose 2}$ with $\frac x{\hat b}\notin A$. Let $x_0$ be the maximal such $x$. Then $\frac{2x_0}{\hat b}\notin A$ as otherwise we would have $\frac{x_0}{\hat b}\in A$ as average of $0$ and $\frac{2x_0}{\hat b}$. But then the maximality of $x_0$ implies $2x_0\ge {p-1\choose 2}$ and that makes $2x_0\le 2\left({p-1\choose 2}-1\right)\le \hat b-{p-1\choose 2}$ by $(2)$ and so $\frac{2x_0}{\hat b}\in A$ again, contradiction. The same argument works with numerators $>\hat b-{p-1\choose 2}$ by averaging against $1$. We conclude $\frac x{\hat b}\in A$ for all $x$, $0\le x\le \hat b$. In particular, $\frac ab=\frac{2^ka}{\hat b}\in A$, contradiction.

Solution 2:

You can easily get all dyadic rationals (rationals expressible with denominator as a power of $2$). In fact these dyadic rationals can always be taken as the average of two other elements in the set. For instance you have $0, 1$. From these two wholes you can get the halfs (just $\frac12$ is new) from the halfs you can get the fourths. From the fourths you can get the eighths. Etc.

I proceed by example, because I'm not sure how to write an exact proof, but I think the ideas are here.

For instance let's try to get some fractions with denominator $5$ as averages of (dyadic) fractions with denominator $8$. We have available $\frac08,\frac18,\frac28,\frac38,\frac48,\frac58,\frac68,\frac78,\frac88$.

If we take a sum of five of these with numerators adding to a multiple of $8$, we will get an average with a denominator of $5$. So for instance $\frac08,\frac18,\frac28,\frac58\frac88$ gives an average of $\frac25$. Or $\frac28,\frac38,\frac48,\frac78,\frac88$ gives an average of $\frac35$. You can't get $\frac45$ using eighths. But you can with sixteenths.

These ideas should generalize, but as I say I am unsure how to write a formal proof. So feel free to improve upon this answer!

Solution 3:

Consider these possibilities:

{0,$\frac{1}{a}$,$\frac{1}{b}$} would average $\frac{a+b}{3ab}$

{1,$\frac{1}{a}$,$\frac{1}{b}$} would average $\frac{ab+a+b}{3ab}$

{$\frac{1}{a}$,$\frac{1}{b}$,$\frac{1}{c}$} would average $\frac{bc+ac+ab}{3abc}$

Consider using, a,b and c as powers of 2 and see what new values you can add.

{0,.5, .125} for a half and an eighth that would give a 24th: $\frac{5}{24}$, (4+1=5)

{1,.5, .125} would give a different 24th for an average here: $\frac{13}{24}$, (8+4+1=13)

Now take the average of {$\frac{13}{24}$,$\frac{1}{8}$} and you'll get $\frac{13+3}{24*2}=\frac{16}{48}= \frac{1}{3}$

Would there exist a similar construct using fractions of an 16th to make a 1 using 5 elements?

6+4+3+2+1=16 where 3/8ths, 1/4th, 3/16ths, 1/8th and 1/16th could be used to derive 1/5th? Granted this is using higher powers of 2 for each number but if there exists a partition of $2^n$ using q or (q-1) parts then it isn't that hard to generate it out.

Averaging with 0 or 1 can produce a few other values as after 1/5 is generated, averaging 1 with it would produce 3/5ths that may generalize.

Solution 4:

Here is a more explicit construction than given in other answers.

As other answers, first notice that it’s quite easy to get all dyadic numbers in $[0,1]$, i.e. numbers of the form $\frac{n}{2^a}$, where $0 \leq n \leq 2^a$.

Now suppose you want to get $\frac{p}{q}$. If you can find $q$ distinct dyadic numbers $x_1$, …, $x_q$ whose sum is exactly $p$, then the average of these will be $\frac{p}{q}$. How can you find those distinct dyadic numbers with the right sum? There are lots of ways to do this, but here’s one. Since the dyadic numbers are dense, you can take them to be close approximations of $\frac{p}{q}$ itself. First pick a denominator $2^a$ to use (for all the $x_i$). Now, using this denominator, take all but one of the numbers $x_i$ to be below $\frac{p}{q}$, but as close as possible to it; and then pick the last number,$x_q$, to be whatever is needed to balance out the total shortfall of the rest, to make the total sum $p$.

We’re nearly done, but not quite. Let’s look at what this method gives for making 1/3. We’re looking for three dyadics with sum 1. With denominator 4, we get 0, 1/4 as the nearest ones below 1/3, and then 3/4 to bring the total up to 1. With denominator 8, we get 1/8, 2/8 as the ones below 3, and then 5/8 as the last number. With denominator 16, we get 4/16, 5/16, and 7/16.

What about for 1/5? We want five dyadics summing to 1, starting with four below 1/5. Trying denominator 4, the four closest aproximations by quarters below 1/5 are… 0, –1/4, –2/4, and –3/4. Oops. By eighths, not much better. By sixteenths, we have 3/16, 2/16, 1/16, and 0/16; and then 10/16 is just right to bring the sum up to 1. Success!

What about for 2/3? We want three dyadics with sum 2. Trying quarters, we get 2/4 and 1/4 as the approximations below it… but then we would need 5/4 to bring the sum up to 2. Trying with eighths, we get 5/8 and 4/8 as the approximations-below; and 7/8 to finish. Success!

Generally, for $\frac{p}{q}$: trying this method, with denominator $2^a$, we get approximations-below of $k/2^a$, $(k-1)/2^a$, …, $(k–q+2)/2^a$, where $k = \lfloor{2^a p / q}\rfloor$, i.e. the largest numerator such that $k/2^a \leq p/q$. Then the last number we pick must bring the sum of the numerators up to $2^a p$, so must be $(2^a p – \sum_{i=0}^{q-2}(k-i))/2^a$.

This will always give a set of $q$ distinct dyadic numbers with average $p/q$. As the examples above show, sometimes some of these dyadics will be outside $[0,1]$. But if you take $a$ large enough (how large? I’ll leave that as an exercise…) then these numbers will be in $[0,1]$, and so you’re done.