Which numbers will remain if I keep removing the second third of the remaining interval?

Question

Inspired by this Google Code Jam problem - Vanishing Numbers

There is a pool of numbers which are arbitrary decimal fractions from the interval (0, 1). In the first round of the game the middle third of the interval disappears, and the numbers from this interval are eliminated from the pool. In the next rounds the middle thirds of each of the remaining intervals disappear. In the first round the the interval [1/3, 2/3] is eliminated and in the second round the two intervals [1/9, 2/9] and [7/9, 8/9] are eliminated, and so on. The endpoints of each removed interval are removed as well.

It seems that if we keep repeating this process, at the end there will still be some fractions that will not get removed, for example 0.3. How to determine which numbers will never get removed, other than by actually repeating the process?

As a hint if you don't want to simply look up a solution, consider trinary representations. — dinoboy, Mar 01 '13 at 15:58
Note that typically in the Cantor set one removes open intervals, whereas in this problem closed intervals are removed. — mdp, Mar 01 '13 at 16:08
@MattPressland Does it matter in this case? Since numbers such as 1/3, 1/9, etc. cannot be represented in decimal fractions — Yohan, Mar 01 '13 at 16:16
It matters a bit. The usual Cantor set includes the numbers that terminate in base $3$ and don't have any $1$'s in the expansion, because $1/3$ is considered as $0.0222222\ldots_3$ instead of $0.1_3$. But it is a countable set, so maybe it doesn't matter for your purpose. — Ross Millikan, Mar 01 '13 at 16:48
@Yohan Not to the answer, but I don't know if other references to the Cantor set will contain statements that break down if you remove the endpoints. — mdp, Mar 01 '13 at 17:32

Alfonso Fernandez · Accepted Answer · 2013-03-01T16:50:37.407

3

If a number $0<x<1$ is represented in base-3 by $0.d_1d_2\ldots$ then the first digit represents in which third it lies, when dividing $(0,1)$ into 3 segments, the second digit represents in which third of that third the number is, etc.

This means, that by the end of the process, you remain with exactly all numbers that have a base-3 representation containing only $0$s and $2$s.

edited Mar 01 '13 at 16:50

answered Mar 01 '13 at 15:59

Alfonso Fernandez

4,047

+1 doing it that way leads to a surprisingly simple treatment of several properties of the cantor set... – gnometorule Mar 01 '13 at 16:08
How do you know if the base-3 representation of a number x contains only 0 and 2? – Yohan Mar 01 '13 at 16:24
This is neat. I've never heard it explained so clearly. – J126 Mar 01 '13 at 16:26
@Yohan If $x$ is rational, its base-3 representation is periodic, and you can simply expand and check. In the general case, the representation may not even be computable, so you can't know. – Alfonso Fernandez Mar 01 '13 at 16:50
@Yohan The representation for the set of all such numbers (the Cantor set), based on this property, would be $\left{\sum_{i=1}^\infty \alpha_i 3^{-i} : \forall i (\alpha_i\in{0,2})\right}$ but this doesn't really capture the essence. – Alfonso Fernandez Mar 01 '13 at 16:57
@AlfonsoFernandez how do I know if the period has repeated? – Yohan Mar 02 '13 at 03:01
@Yohan Just like in base-10 long division, just with all the numbers written in base-3. – Alfonso Fernandez Mar 02 '13 at 12:59

Which numbers will remain if I keep removing the second third of the remaining interval?

1 Answers1