A set $Q$ contains $0$, $1$ and the average of all elements of every finite non-empty subset of $Q$. Prove that $Q$ contains all rational numbers in $[0,1]$.

This is the exact wording, as it was given to me. Obviously, the elements that correspond to the average, are rational, since they can be expressed as $\frac{(q_1+q_2+\dots q_k)}{k}$, where $0\leq k\leq1$. But I don't know how to proceed.

  • $\begingroup$ @5xum thanks for the edit! I am new here and not very familiar with the editor! $\endgroup$ – Carlos Lopez Sep 29 '17 at 10:10
  • 1
    $\begingroup$ Just a quick comment - I would change your subscript on the $q_k$ to avoid using $k$ with two different meanings :-) $\endgroup$ – TheMathsGeek Sep 29 '17 at 10:12
  • $\begingroup$ You shouldn't have $0\leq k\leq 1$, it's the $q$'s that are between $0$ and $1$, not the index. $\endgroup$ – Michael Burr Sep 29 '17 at 10:32

Let's explore the first few possibilities to see what's going on.

  • You already know that $Q$ contains $0$ and $1$.

  • The average of $0$ and $1$ is $\frac{1}{2}$, so this is in $Q$ too.

  • The average of $0$ and $\frac{1}{2}$ is $\frac{1}{4}$ and the average of $\frac{1}{2}$ and $1$ is $\frac{3}{4}$.

  • For $\frac{1}{3}$, we see that this is the average of $0$, $\frac{1}{4}$, and $\frac{3}{4}$. Similarly, $\frac{2}{3}$ is the average of $1$, $\frac{3}{4}$, and $\frac{1}{4}$.

Now, let's prove this more completely (although somewhat sketchy because the complete rigor is somewhat messy).

Step 1: Prove that all dyadic numbers are in this set. A dyadic number is a fraction of the form $\frac{a}{2^n}$ for integer $a$ and some natural number $n$. For our case, it is safe to assume that $a$ is odd and that $0<a<2^n$.

Proof by induction on $n$, the only dyadic number (satisfying the conditions) when $n=1$ is $\frac{1}{2}$, which is the average of $0$ and $1$.

Inductive step, consider the dyadic number $\frac{a}{2^{n+1}}$. We can observe that this is the average of $\frac{a+1}{2^{n+1}}$ and $\frac{a-1}{2^{n+1}}$. Note that both $a+1$ and $a-1$ are even, so these are actually dyadic numbers with smaller denominators, so they are in the set by the inductive hypothesis (if $a+1=2^{n+1}$ or $a-1=0$, then these numbers are $0$ or $1$, which are given to be in the set).

Step 2: Prove that all rational numbers are in the set using dyadic numbers.

Let $\frac{p}{q}$ be an arbitrary rational number. To get this rational number, it must be an average of $q$ numbers whose sum is $p$. We can write $p$ as a sum of dyadic numbers in the following way:

Choose $p$ dyadic numbers that are all near $1$, for example, $\frac{2^n-1}{2^n}$. With various $n$'s large enough, the difference between the sum of these numbers and $p$ is a small (close to zero) dyadic number. It would be of the form $\frac{a}{2^n}$ for $a$ relatively small.

We now need to write $\frac{a}{2^n}$ as a sum of $q-p$ dyadic numbers. We can rewrite this fraction as $\frac{a2^m}{2^{n+m}}$ so that $a2^m$ is larger than $q-p$, let this be $\frac{b}{2^{n+m}}$, observe that this is the sum of $\frac{b-1}{2^{n+m+1}}$ and $\frac{b+1}{2^{n+m+1}}$. By repeatedly splitting the smallest element of the set in this way until you have $q-p$ elements, you have a collection whose average is $\frac{p}{q}$. Note that by the choice of $b$, you'll never reach $0$ using this splitting technique (and that all of the numbers are distinct).

  • $\begingroup$ you are a genius! $\endgroup$ – Carlos Lopez Sep 29 '17 at 10:48
  • $\begingroup$ You might want to try alternate constructions for $\frac{p}{q}$, different approaches might give an expression that's easier to write down. $\endgroup$ – Michael Burr Sep 29 '17 at 11:04

By successively taking midpoints we can produce all numbers of the form $${k\over2^n}\qquad(n\geq0, \ 0\leq k\leq 2^n)\ .$$ Now let two numbers $0<p<q$ be given. Write $q-p=:p'$ for simplicity. Choose a sufficiently large $n$ (see below), and put $$k_i:=i-1\quad(0< i\leq p'),\qquad k_{q-i}:=2^n-i\quad(0\leq i<p)\ .$$ One then has $$\sum_{i=1}^q k_i=p\cdot 2^n+{(p'-1)p'\over2}-{(p-1)p\over2}=:p\cdot 2^n+\Delta\ .$$ Note that $|\Delta|<{q^2\over2}$. If $\Delta>0$ replace the first "large" $k_i\,$, namely $k_{p'+1}$, by $\ k_{p'+1}^{\rm new}:=k_{p'+1}-\Delta$. If $n$ is large enough then one still has $k_{p'+1}^{\rm new}>k_{p'}$. Make a similar correction if $\Delta<0$. The numbers $$x_i:={k_i\over 2^n}\in Q\quad(1\leq i\leq q)$$ now form an increasing sequence of $q$ different numbers, and one has $${1\over q}\sum_{i=1}^q x_i={1\over q\cdot 2^n}\sum_{i=1}^q k_i={p\cdot 2^n\over q\cdot 2^n}={p\over q}\ ,$$ hence ${p\over q}\in Q$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.