Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a question that is something I am wondering for some time now and I couldn't even begin answering it. I guess it could be called a riddle.

So, let $x\in[0,1]$ and $k\in(0,1)$. We begin at $x$ and we say that we make a "step up" by going to $x+k(1-x)$ and we make a "step down" by going to $x-kx$. Notice that whatever $x$ and $k$ we choose we have $x-kx\in[0,1]$ and $x+k(1-x)\in[0,1]$.

Then let $X_0=\{x\}$ and $X_{n+1}=\bigcup_{x\in X_n}\{x,x-kx,x+k(1-x)\}$. So $X_{n+1}$ is the set we get if we add the "up step" and the "down step" of every element of $X_n$ to $X_n$.

Let $X_\infty=\lim_{n\to\infty}X_n$. So my question is: Is $\overline{X_\infty}=[0,1]$?

Another related question I couldn't also answer is: By beginning at an arbitrary $x$ is there any (finite) number of steps one can make to get back exactly to $x

Also I am not really sure about the tags, so feel free to modify them.

share|cite|improve this question
In general, no. For example, $x=0$ and $k=0$. Maybe it holds if you restrict $x \in (0,1)$ and $k \in (0,1)$? – madprob Nov 11 '12 at 4:34
Oh, well, ok. I changed it. – tst Nov 11 '12 at 5:05
It makes the symmetry of the operations a bit clearer to set $K=1-k$ and consider $x\mapsto Kx$ and $x\mapsto 1-K(1-x)$. – Henning Makholm Nov 11 '12 at 15:23
up vote 6 down vote accepted

No, the result is not dense for all $k\in(0,1)$. One particular value where it is not dense is $k=2/3$.

To see this, imagine the $x$'s written as base-3 fractions. Then $x\mapsto x-kx=\frac13x$ corresponds to inserting a 0 after the fraction point and shifting all of the existing trits one position to the right. And $x\mapsto x+k(1-x)=\frac23+\frac13x$ corresponds to inserting a 2 after the fraction point and also shifting all of the existing trits one position to the right.

Therefore, except from the countably many points that are hit exactly, the only numbers that can be approximated by the sequence are the Cantor set.

More primitively, for any $k>1/2$ there is an interval around $x=1/2$ that can never be hit by either of the two operations, and so $X_\infty$ is certainly not dense in that interval.

On the other hand, a very similar argument shows that the result for $k=1/2$ is dense.I suspect that $\overline{X_\infty}=[0,1]$ for all $k\in (0,1/2]$.

Added later: In fact, this construction generalizes directly to any $k\in(0,\frac 12]$. Proof sketch:

  1. For any infinite sequence $(a_n)$ of $0$s and $1$s, consider the series $$\tag{*}A=\sum_{n=0}^\infty k(1-k)^na_n $$ and assuming it converges say that $(a_n)$ is a "modified binary expansion" of $A$.

  2. If we know a modified binary expansion for $A$, then the possible successors of $A$ under your step rules have modified binary expansions that arise by shifting the one for $A$ one position to the right and putting either $0$ or $1$ in front of it. (To prove this just factor one $(1-k)$ out of the series for the two successor expansions, and simplify).

  3. Prove that every $A\in[0,1]$ has at least one modified binary expansion (actually continuum many such expansions in most cases, but that is not important). To do so, just choose the bits one by one, such whenever we have chosen $a_0$ through $a_m$, the interval $$I_m = \left[\sum_{n=0}^m k(1-k)^na_n,\quad (1-k)^m+\sum_{n=0}^m k(1-k)^na_n \right]$$ contains $A$. We can continue doing that forever, because the union of the two possibilities for $I_{m+1}$ is exactly $I_m$ (here is where we use $k\le\frac 12$). Also, the length of the $I_m$s go towards zero (because $k>0$), so the partial sums of $(*)$ must converge towards $A$.

  4. Choose some modified binary expansion $(x_n)$ for your starting $x$. Then $X_\infty$ consists exactly of those numbers that have modified binary expansions of the form $(b_0,b_1,\ldots,b_m,x_0,x_1,\ldots)$ for some $m\ge 0$ and some $b_n$s in ${0,1}$.

  5. Let $Y\in[0,1]$ be arbitary; we wish so show $Y\in\overline{X_\infty}$. Now $Y$ must have a modified binary expansion $(y_n)$. Then for each $m\in\mathbb N$, let $$ Q_m = \left(\sum_{n=0}^m k(1-k)y_n\right)+(1-k)^{m+1}x$$ It is clear that $Y$ is the limit of the $Q_m$s, and each $Q_m$ is in $X_\infty$ because it has the modified binary expansion $(y_0,y_1,\ldots,y_m,x_0,x_1,\ldots)$

share|cite|improve this answer
This a very clever construction. Thank you very much. However couldn't find a proof that this happens for any $k\in(0,\frac{1}{2}]$. – tst Nov 20 '12 at 16:08
@tst: It actually generalizes fairly straightforwardly. See edited answer. – Henning Makholm Nov 20 '12 at 18:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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