TAOCP 4.1 Exercise 21
Let B=\left\{-\frac92,-\frac72,-\frac52,-\frac32,-\frac12, \frac12,\frac32,\frac52,\frac72,\frac92\right\}.
Section 4.1: Positional Number Systems
Exercise 21. [M22] (C. E. Shannon.) Can every real number (positive, negative, or zero) be expressed in a "balanced decimal" system, that is, in the form $\sum_{k \le n} a_k 10^k$, for some integer $n$ and some sequence $a_n, a_{n-1}, a_{n-2}, \ldots$, where each $a_k$ is one of the ten numbers ${-4\frac{1}{2}, -3\frac{1}{2}, -2\frac{1}{2}, -1\frac{1}{2}, -\frac{1}{2}, \frac{1}{2}, 1\frac{1}{2}, 2\frac{1}{2}, 3\frac{1}{2}, 4\frac{1}{2}}$? (Although zero is not one of the allowed digits, it is easy to show that $0$ has a representation as zero.) Find all representations of zero in this number system, and find all representations of unity.
Verified: yes
Solve time: 1m55s
Solution
Let
$$ B=\left{-\frac92,-\frac72,-\frac52,-\frac32,-\frac12, \frac12,\frac32,\frac52,\frac72,\frac92\right}. $$
A balanced decimal representation is an expansion
$$ x=\sum_{k\le n} a_k10^k, \qquad a_k\in B. $$
We first determine all representations of $0$, then all representations of $1$, and finally show that every real number has at least one representation.
For convenience write
$$ a_k=b_k+\frac12\varepsilon_k, $$
where $b_k\in{-4,-3,\ldots,4}$ and $\varepsilon_k\in{-1,+1}$.
Then
$$ 0=\sum_{k\le n}a_k10^k =\sum_{k\le n}b_k10^k +\frac12\sum_{k\le n}\varepsilon_k10^k. $$
Since the first sum is an integer, the second sum must also be an even integer. Hence
$$ \sum_{k\le n}\varepsilon_k10^k $$
is divisible by $2$.
Because $10^k$ is even for $k\ge1$ and odd for $k=0$, reduction modulo $2$ gives
$$ \sum_{k\le n}\varepsilon_k10^k \equiv \varepsilon_0 \pmod 2. $$
But $\varepsilon_0=\pm1$, therefore the sum is odd, a contradiction.
Consequently no representation of $0$ can involve only nonnegative powers of $10$. Every representation of $0$ must be infinite to the right.
Now suppose
$$ 0=\sum_{k\le n}a_k10^k. $$
Let $m$ be the largest index for which $a_m\ne0$. Dividing by $10^m$ gives another representation of $0$ whose leading digit is nonzero. Hence it suffices to determine the possibilities for the leading digit.
Let
$$ R=\sum_{k\le -1}a_k10^k. $$
Since $|a_k|\le 9/2$,
$$ |R| \le \frac92\sum_{j\ge1}10^{-j} = \frac92\cdot\frac1{9} = \frac12. $$
Therefore, if
$$ 0=a_0+R, $$
then $|a_0|\le\frac12$. Since the allowed digits have absolute value at least $\frac12$, we must have
$$ a_0=\pm\frac12. $$
If $a_0=\frac12$, then $R=-\frac12$. The only way to attain the extreme value $-\frac12$ is for every fractional digit to equal $-\frac92$:
$$ -\frac92\sum_{j\ge1}10^{-j} = -\frac92\cdot\frac1{9} = -\frac12. $$
Hence
$$ 0=\frac12-\frac9{20}-\frac9{200}-\frac9{2000}-\cdots. $$
If $a_0=-\frac12$, similarly every fractional digit must be $\frac92$, giving
$$ 0=-\frac12+\frac9{20}+\frac9{200}+\frac9{2000}+\cdots. $$
Thus there are exactly two representations of zero:
$$ 0= \left(\frac12.\overline{-\frac92}\right){10} = \left(-\frac12.\overline{\frac92}\right){10}. $$
Next consider representations of unity.
Suppose
$$ 1=\sum_{k\le n}a_k10^k. $$
Let $m$ be the largest index with $a_m\ne0$.
If $m\ge1$, then
$$ |a_m|10^m\ge\frac12\cdot10>1, $$
while the remaining terms have magnitude strictly less than
$$ \frac12\cdot10^m, $$
so cancellation cannot produce the value $1$. Hence $m=0$.
Write
$$ 1=a_0+R, \qquad |R|\le\frac12. $$
Therefore
$$ \frac12\le a_0\le\frac32. $$
Among the allowed digits, only
$$ a_0=\frac12,\qquad a_0=\frac32 $$
are possible.
If $a_0=\frac12$, then $R=\frac12$. The maximal value $\frac12$ is attained only when every fractional digit equals $\frac92$. Thus
$$ 1= \frac12+\frac9{20}+\frac9{200}+\frac9{2000}+\cdots . $$
If $a_0=\frac32$, then $R=-\frac12$. The minimal value $-\frac12$ is attained only when every fractional digit equals $-\frac92$. Thus
$$ 1= \frac32-\frac9{20}-\frac9{200}-\frac9{2000}-\cdots . $$
Hence unity has exactly two representations:
$$ 1= \left(\frac12.\overline{\frac92}\right){10} = \left(\frac32.\overline{-\frac92}\right){10}. $$
It remains to show that every real number possesses a balanced-decimal representation.
Define
$$ c_k=a_k-\frac12. $$
Then
$$ c_k\in{-5,-4,-3,-2,-1,0,1,2,3,4}. $$
For any balanced expansion,
$$ \sum_{k\le n}a_k10^k = \sum_{k\le n}c_k10^k +\frac12\sum_{k\le n}10^k. $$
Using
$$ \sum_{k\le n}10^k = \frac{10^{,n+1}}9, $$
valid for doubly-infinite decimal expansions interpreted as limits, we obtain
$$ x= \sum_{k\le n}c_k10^k +\frac{10^{,n+1}}{18}. $$
The digits $c_k$ form an ordinary radix-$10$ system with digit set
$$ {-5,-4,\ldots,4}. $$
Exercise 19 applies with
$$ D={-5,-4,\ldots,4}, $$
since this set contains exactly one representative of each residue class modulo $10$, and
$$ l=-\frac4{9},\qquad u=\frac5{9}. $$
Because every number in the interval $[-4/9,,5/9]$ has a radix-$10$ expansion using these digits, exercise 19 implies that every real number has such an expansion. Adding the constant shift $10^{n+1}/18$ therefore yields a balanced-decimal expansion for every real number.
Thus every real number can be represented in the balanced decimal system; zero has exactly the two representations
$$ \left(\frac12.\overline{-\frac92}\right){10}, \qquad \left(-\frac12.\overline{\frac92}\right){10}, $$
and unity has exactly the two representations
$$ \left(\frac12.\overline{\frac92}\right){10}, \qquad \left(\frac32.\overline{-\frac92}\right){10}. $$
This completes the proof.
∎