Problem:
Given 0âĪx0â<1, let
xnâ={2xnâ1â2xnâ1ââ1â if 2xnâ1â<1 if 2xnâ1ââĨ1â
for all integers n>0. For how many x0â is it true that x0â=x5â?
Answer Choices:
A. 0
B. 1
C. 5
D. 31
E. infinitely many
Solution:
When a number x0ââ[0,1) is written in base-two, it has the form
x0â=0.d1âd2âd3âd4âd5âd6âd7ââĶ (each dkâ=0 or 1.)
The algorithm given in the problem simply moves the "binary point" one place to the right and then ignores any digits to the left of the point. That is
x0â=0.d1âd2âd3âd4âd5âd6âd7ââĶâđx1â=0.d2âd3âd4âd5âd6âd7ââĶ
Thus for x0â to equal x5â we must have
āļ. d1âd2âd3âd4âd5âd6âd7ââĶ=0.d6âd7âd8âd9âd10âd11âd12ââĶ
This happens if and only if x0â has a repeating expansion with d1âd2âd3âd4âd5â as the repeating block. There are 25=32 such blocks. However, if d1â= d2â=d3â=d4â=d5â=1, then x0â=1. Hence there are 32â1=31 values of x0ââ[0,1) for which x0â=x5â.
OR
We can restate the given formula as xnâ=2xnâ1âââ2xnâ1ââ, where âtâ is the largest integer not exceeding t. Since ât+kâ=âtâ+k for any integer k, it follows that
x5â====â2x4âââ2x4ââ2(2x3âââ2x3ââ)ââ2(2x3âââ2x3ââ)â=4x3ââ2â2x3ââââ4x3ââ+2â2x3ââ4x3âââ4x3âââŪ32x0âââ32x0ââ.â
Consequently, to have x5â=x0â it is necessary that 31x0â=â32x0ââ be an integer. But 31x0â is an integer for some x0â in the prescribed domain precisely when x0â=n/31 for some n=0,1,âĶ,30. It is easy to check that for each of these 31 values of x0â we have x5â=x0â.