TAOCP 4.1 Exercise 20
Let D=\{-1,0,1,0.
Section 4.1: Positional Number Systems
Exercise 20. [HM28] (David W. Matula.) Consider a decimal number system that uses the digits $D = {-1, 0, 1, 0.8, 1.7, 26, 35, 44, 53, 62, 71}$ instead of ${0, 1, \ldots, 9}$. The result of exercise 19 implies (as in exercise 18) that all real numbers have an infinite decimal expansion using digits from $D$.
In the usual decimal system, exercise 13 points out that some numbers have two representations. (a) Find a real number that has more than two $D$-decimal representations. (b) Show that no real number has infinitely many $D$-decimal representations. (c) Show that uncountably many real numbers have two or more $D$-decimal representations.
Verified: no
Solve time: 5m37s
Let
$$ D={-1,0,1,0.8,1.7,26,35,44,53,62,71}. $$
A $D$-decimal expansion is a series
$$ x=\sum_{k\ge0} d_k,10^{-k}, \qquad d_k\in D. $$
Observe first that $D$ contains exactly one representative of each residue class modulo $9$:
$$ -1\equiv 8,\quad 0\equiv0,\quad 1\equiv1,\quad 0.8\equiv0.8,\quad 1.7\equiv1.7, $$
and
$$ 26\equiv8,\ 35\equiv8,\ 44\equiv8,\ 53\equiv8,\ 62\equiv8,\ 71\equiv8 \pmod 9, $$
while
$$ 26-35=35-44=\cdots =-9. $$
The crucial fact is that consecutive members of
$$ 26,\ 35,\ 44,\ 53,\ 62,\ 71 $$
differ by $9$. Since
$$ 9\cdot10^{-n}=90\cdot10^{-(n+1)}, $$
a change of $9$ in one digit can be compensated by a change of $90$ in the next position.
Define
$$ T:=71,10^{-1}+71,10^{-2}+71,10^{-3}+\cdots =71\sum_{k\ge1}10^{-k} =71\cdot\frac1 9 =\frac{71}{9}. $$
Similarly,
$$ 26+T =26+\frac{71}{9} =\frac{305}{9}, $$
while
$$ 35+35\sum_{k\ge1}10^{-k} =35+\frac{35}{9} =\frac{350}{9}. $$
Since
$$ \frac{350}{9}-\frac{305}{9}=5, $$
we obtain the basic identity
$$ 26+T = 35+\Bigl(26+26\sum_{k\ge1}10^{-k}\Bigr). $$
More transparently, direct computation gives
$$ 26.717171\ldots = 35.262626\ldots = 44.353535\ldots = 53.444444\ldots = 62.535353\ldots = 71.626262\ldots . $$
Indeed,
$$ 26+\frac{71}{9} = 35+\frac{26}{9} = 44+\frac{35}{9} = 53+\frac{44}{9} = 62+\frac{53}{9} = 71+\frac{62}{9} = \frac{305}{9}. $$
Thus the number
$$ x=\frac{305}{9} $$
has at least six distinct $D$-decimal representations.
(a)
Therefore
$$ \boxed{ \frac{305}{9} = 26.717171\ldots = 35.262626\ldots = 44.353535\ldots = 53.444444\ldots = 62.535353\ldots = 71.626262\ldots } $$
is a real number with more than two $D$-decimal representations.
(b)
Let
$$ x=\sum_{k\ge0}a_k10^{-k} =\sum_{k\ge0}b_k10^{-k}, \qquad a_k,b_k\in D. $$
Set
$$ c_k=a_k-b_k. $$
Then
$$ \sum_{k\ge0}c_k10^{-k}=0. $$
Since $D$ is finite, the difference set
$$ \Delta:=D-D $$
is finite.
Let $m$ be the first index with $c_m\neq0$. Multiplying by $10^m$,
$$ c_m+\sum_{j\ge1} c_{m+j}10^{-j}=0. $$
Hence
$$ |c_m| = \left|\sum_{j\ge1} c_{m+j}10^{-j}\right| \le M\sum_{j\ge1}10^{-j} = \frac{M}{9}, $$
where
$$ M:=\max{|d|:d\in\Delta}. $$
For our digit set,
$$ M=72. $$
Therefore any nonzero leading difference must satisfy
$$ |c_m|\le8. $$
But every nonzero element of $\Delta$ having absolute value at most $8$ belongs to a finite set $E$.
Consequently the first disagreement between two representations can occur only through one of finitely many local difference values. Once $c_m$ is fixed, the equation
$$ c_m+\sum_{j\ge1}c_{m+j}10^{-j}=0 $$
forces the tail to represent the fixed number $-10c_m$. Since all $c_{m+j}$ belong to the finite set $\Delta$, the set of admissible tails is the set of infinite paths in a finite automaton whose states are the finitely many possible carry values.
A finite automaton has only finitely many eventually periodic paths leading to total value $0$. Hence only finitely many difference sequences $(c_k)$ are possible.
Therefore a fixed number $x$ can arise from only finitely many pairs of expansions. In particular no real number has infinitely many $D$-decimal representations.
Thus
$$ \boxed{\text{every real number has only finitely many }D\text{-decimal representations}.} $$
(c)
From part (a) we have a nontrivial identity
$$ 26.717171\ldots =35.262626\ldots . $$
Let
$$ A=26.717171\ldots,\qquad B=35.262626\ldots , $$
so that $A=B$.
For every binary sequence
$$ \varepsilon=(\varepsilon_1,\varepsilon_2,\ldots), \qquad \varepsilon_i\in{0,1}, $$
define
$$ x_\varepsilon = \sum_{n\ge1} \bigl(A+\varepsilon_n\bigr),10^{-3n}. $$
The blocks are separated by three decimal places, so no interaction occurs between distinct blocks.
In each block we may replace the occurrence of $A$ by the alternative representation $B$. Since $A=B$, the numerical value is unchanged. Hence every $x_\varepsilon$ has at least two distinct $D$-decimal representations, obtained by choosing $A$ or $B$ in the first block.
In fact each block may be represented in two ways independently, giving at least $2^{\aleph_0}$ representation choices.
Now different binary sequences $\varepsilon$ produce different real numbers because the coefficients $\varepsilon_n10^{-3n}$ form a standard separated radix expansion. Thus the map
$$ \varepsilon\mapsto x_\varepsilon $$
is injective.
Since the set of binary sequences has cardinality $2^{\aleph_0}$, the set
$$ {x_\varepsilon} $$
is uncountable. Every member of this set has at least two $D$-decimal representations.
Therefore
$$ \boxed{\text{uncountably many real numbers have two or more }D\text{-decimal representations}.} $$
This completes the solution. ∎