Generating the Rationals

4 Apr 2012

Here is the problem for tonight:

A set S contains 0 and 1, and the mean of every finite non-empty subset of S. Prove that S contains all the rational numbers in the unit interval.

Ok….

Let's clarify what the rational number is. Maybe we'll get some ideas out of it.

A rational number is in the form of a/b where a and b are integer.

I still got nothing.

So, `S` contains all the rational numbers in [0,1]. It implies that it might also contain non-rational numbers, as well, but we might not care about it.

I still got nothing.

So, `Scontains 0 and 1, and the mean of a set, whose members are also the member of ``S```.

It surely sounds like the barber paradox.

A mean of `{ a, b, c, d }is ``(a + b + c + d) / 4`. A mean is guaranteed to be rational ifa``, `b, ``c`, andd`` are all rational.

Walla! This is good shit.

`S` contains only rational numbers (Wrong!)

Let's assume that `Scontains an irrational number ``a```.

Ok, this is a wrong direction. I cannot prove anything out of it. Let's try again -------------------- How about I claim that we can derive any ```a/b``` where ```a <= b``` ### Base case

Complex case

Still got nothing. Let's try again ----------------------- Ok, we are using a contradiction this time. Let's assume that ```a/b``` is not a member of ```S```. This means that there is no set ```{ c[1], ..., c[n] }``` that has its mean equal to ```a/b```.

Still got nothing.

Let's try again

Induction!

If we have 0/n, 1/n, ..., n/n, we can calculate 0/(n+1), 1/(n+1), ..., (n+1)/(n+1) ```0/(n+1)``` is ```0/n```. Ok!

Let's rephrase it to:

How do we calculate a/n from b/m where m > n?

If `n = 2k(an even number), assuming that ``a = c + d (c != d)`, we get thata/n = c/2k + d/2k = (c/k + d/k)/2``. This case is ok.

If `n = 2k+1(an odd number), assuming that ``a = c + d (c != d)```, we get nothing…

I gave up ------------------- So.. The book starts with ```S``` contains all ```p/(2^n)```. Ok, that's easy to see. Basically, it claims that ```p/q``` can by the mean of ```x/(2^n)```. Now this is getting a little weird.

We choose a very very large `n` and replace 1 with 1-1/(2n), 1+1/(2n), 1-2/(2^n), and so on.

For example, 1/7 = (1-1/(2n) + 0+1/(2n) + 0-2/(2n) + 0+2/(2n) + 0-3/(2n) + 0+3/(2n) + 0) / 7

And that's it.

This is tooo creative.

Give it a kudos