Changed layout for more manageable volumes

1 files changed, 1922 insertions, 0 deletions

diff --git a/vol2/4.1.lyx b/vol2/4.1.lyx
new file mode 100644
index 0000000..b68ec0b
--- /dev/null
+++ b/vol2/4.1.lyx
@@ -0,0 +1,1922 @@
+#LyX 2.4 created this file. For more info see https://www.lyx.org/
+\lyxformat 620
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\begin_preamble
+\input defs
+\end_preamble
+\use_default_options true
+\maintain_unincluded_children no
+\language english
+\language_package default
+\inputencoding utf8
+\fontencoding auto
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_roman_osf false
+\font_sans_osf false
+\font_typewriter_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\float_placement class
+\float_alignment class
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_formatted_ref 0
+\use_minted 0
+\use_lineno 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style english
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tablestyle default
+\tracking_changes false
+\output_changes false
+\change_bars false
+\postpone_fragile_content false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\docbook_table_output 0
+\docbook_mathml_prefix 1
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc2[24]
+\end_layout
+
+\end_inset
+
+Consider the following four number systems:
+\end_layout
+
+\begin_layout Enumerate
+binary (signed magnitude);
+\end_layout
+
+\begin_layout Enumerate
+negabinary (radix 
+\begin_inset Formula $-2$
+\end_inset
+
+);
+\end_layout
+
+\begin_layout Enumerate
+balanced ternary;
+ and
+\end_layout
+
+\begin_layout Enumerate
+radix 
+\begin_inset Formula $b=\frac{1}{10}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Use each of these four number systems to express each of the following three numbers:
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $-49$
+\end_inset
+
+;
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $-3\frac{1}{7}$
+\end_inset
+
+ (show the repeating cycle);
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $\pi$
+\end_inset
+
+ (to a few significant figures).
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $-49\to-110001$
+\end_inset
+
+.
+ Multiplying by 2,
+ 
+\begin_inset Formula $\frac{1}{7}\to\frac{2}{7}\to\frac{4}{7}\to1+\frac{1}{7}$
+\end_inset
+
+,
+ so 
+\begin_inset Formula $-3\frac{1}{7}\to-11.\overbrace{001}$
+\end_inset
+
+.
+ Finally,
+ 
+\begin_inset Formula $\pi\to11.00100100001111...$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+The trick is to express the number in binary and,
+ for the odd positions (the ones where 
+\begin_inset Formula $(-2)^{k}$
+\end_inset
+
+ is negative),
+ add 1 to the part of the number on the right,
+ because we are subtracting 
+\begin_inset Formula $2^{k}$
+\end_inset
+
+ instead of adding so we compensate for that.
+ For negative numbers,
+ we represent them in two's complement before this change,
+ effectively adding 
+\begin_inset Formula $2^{M}$
+\end_inset
+
+ for some large 
+\begin_inset Formula $M$
+\end_inset
+
+,
+ and after it we drop that upper bit to subtract 
+\begin_inset Formula $2^{M}$
+\end_inset
+
+.
+ Thus 
+\begin_inset Formula $-49\to...111001111\to11010011$
+\end_inset
+
+,
+ 
+\begin_inset Formula $-3\frac{1}{7}\to...1100.\overbrace{110110}\to1101.\overbrace{001011}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\pi\to111.01100100010000...$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+We proceed as in the text:
+ 
+\begin_inset Formula 
+\begin{align*}
+-49 & \to-1211\to...11102200\to\overline{1}11\overline{1}\overline{1};\\
+-3\frac{1}{7} & \to-10.\overbrace{010212}\to\dots1101.\overbrace{100122}\to\overline{1}0.\overbrace{0\overline{1}\overline{1}011};\\
+\pi & \to10.010211012\dots\to...1121.122022201\dots\to10.011\overline{1}111\overline{1}0\dots.
+\end{align*}
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+This is like the decimal system but backwards,
+ so 
+\begin_inset Formula $-49\to-9.4$
+\end_inset
+
+,
+ 
+\begin_inset Formula $-3\frac{1}{7}\to-\overbrace{758241}3$
+\end_inset
+
+,
+ 
+\begin_inset Formula $\pi\to...51413$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+exerc5[00]
+\end_layout
+
+\end_inset
+
+Explain why a negative integer in nines' complement notation has a representation in ten's complement notation that is always one greater,
+ if the representations are regarded as positive.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Ten's complement of a negative number 
+\begin_inset Formula $s$
+\end_inset
+
+ is 
+\begin_inset Formula $10^{M}+s$
+\end_inset
+
+,
+ for a suitably large integer 
+\begin_inset Formula $M$
+\end_inset
+
+,
+ while nines' complement is 
+\begin_inset Formula $(10^{M}-1)+s$
+\end_inset
+
+,
+ so the ten's complement is one greater.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+exerc8[M10]
+\end_layout
+
+\end_inset
+
+Prove Eq.
+ (5).
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+The part at the left is 
+\begin_inset Formula $\sum_{j}a_{j}b^{j}$
+\end_inset
+
+,
+ while the part at the right is 
+\begin_inset Formula $\sum_{j}A_{j}b^{kj}$
+\end_inset
+
+,
+ but 
+\begin_inset Formula $A_{j}=\sum_{i=0}^{k-1}a_{kj+i}b^{i}$
+\end_inset
+
+,
+ so this is
+\begin_inset Formula 
+\[
+\sum_{j}A_{j}b^{kj}=\sum_{j}\sum_{i=0}^{k-1}(a_{kj+i}b^{i})b^{kj}=\sum_{j}\sum_{i=0}^{k-1}(a_{kj+i}b^{kj+i})=\sum_{j}a_{j}b^{j}.
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc9[15]
+\end_layout
+
+\end_inset
+
+Change the following 
+\emph on
+octal
+\emph default
+ numbers to 
+\emph on
+hexadecimal
+\emph default
+ notation,
+ using the hexadecimal digits 
+\family typewriter
+0
+\family default
+,
+ 
+\family typewriter
+1
+\family default
+,
+ ...,
+ 
+\family typewriter
+9
+\family default
+,
+ 
+\family typewriter
+A
+\family default
+,
+ 
+\family typewriter
+B
+\family default
+,
+ 
+\family typewriter
+C
+\family default
+,
+ 
+\family typewriter
+D
+\family default
+,
+ 
+\family typewriter
+E
+\family default
+,
+ 
+\family typewriter
+F
+\family default
+:
+ 12;
+ 5655;
+ 2550276;
+ 76545336;
+ 3726755.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+We use Eq.
+ (5) with base 2.
+\end_layout
+
+\begin_layout Standard
+\align center
+\begin_inset Tabular
+<lyxtabular version="3" rows="6" columns="3">
+<features tabularvalignment="middle">
+<column alignment="right" valignment="top">
+<column alignment="right" valignment="top">
+<column alignment="right" valignment="top">
+<row>
+<cell alignment="right" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+Octal
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="right" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+Binary
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="right" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+Hexadecimal
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+12
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+1 010
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="right" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family typewriter
+A
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+5655
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+101 110 101 101
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="right" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family typewriter
+BAD
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+2550276
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+10 101 101 000 010 111 110
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="right" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family typewriter
+AD0BE
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+76545336
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="right" valignment="top" topline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+111 110 101 100 101 011 011 110
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="right" valignment="top" topline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family typewriter
+FACADE
+\end_layout
+
+\end_inset
+</cell>
+</row>
+<row>
+<cell alignment="right" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+3726755
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="right" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+11 111 010 110 111 101 101
+\end_layout
+
+\end_inset
+</cell>
+<cell alignment="right" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none">
+\begin_inset Text
+
+\begin_layout Plain Layout
+
+\family typewriter
+FADED
+\end_layout
+
+\end_inset
+</cell>
+</row>
+</lyxtabular>
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Note Comment
+status open
+
+\begin_layout Plain Layout
+Is this what academics do when they get bored?
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc13[M21]
+\end_layout
+
+\end_inset
+
+In the decimal system there are some numbers with two infinite decimal expansions;
+ for example,
+ 
+\begin_inset Formula $2.3599999...=2.3600000...$
+\end_inset
+
+.
+ Does the 
+\emph on
+negadecimal
+\emph default
+ (base 
+\begin_inset Formula $-10$
+\end_inset
+
+) system have unique expansions,
+ or are there real numbers with two different infinite expansions in this base also?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+There are real numbers with two different infinite expansions:
+ 
+\begin_inset Formula 
+\[
+\tfrac{1}{11}=0.090909...=(0.090909...)_{-10}=(1.909090...)_{-10}.
+\]
+
+\end_inset
+
+Effectively,
+ 
+\begin_inset Formula $(0.090909...)_{-10}=\sum_{k\geq1}9\cdot(-10)^{-2k}=9\sum_{k\geq1}100^{-k}=9\frac{\frac{1}{100}}{\frac{99}{100}}=\frac{1}{11}$
+\end_inset
+
+,
+ but 
+\begin_inset Formula $(1.909090...)_{-10}=1+\sum_{k\geq1}9\cdot(-10)^{-2k+1}=1-90\sum_{k\geq1}100^{-k}=1-90\frac{1}{99}=1-\frac{10}{11}=\frac{1}{11}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc19[23]
+\end_layout
+
+\end_inset
+
+(David W.
+ Matula.) Let 
+\begin_inset Formula $D$
+\end_inset
+
+ be a set of 
+\begin_inset Formula $b$
+\end_inset
+
+ integers,
+ containing exactly one solution to the congruence 
+\begin_inset Formula $x\equiv j\pmod b$
+\end_inset
+
+ for 
+\begin_inset Formula $0\leq j<b$
+\end_inset
+
+.
+ Prove that all integers (positive,
+ negative,
+ or zero) can be represented in the form 
+\begin_inset Formula $m=(a_{n}\dots a_{0})_{b}$
+\end_inset
+
+,
+ where all the 
+\begin_inset Formula $a_{j}$
+\end_inset
+
+ are in 
+\begin_inset Formula $D$
+\end_inset
+
+,
+ if and only if all integers in the range 
+\begin_inset Formula $l\leq m\leq u$
+\end_inset
+
+ can be so represented,
+ where 
+\begin_inset Formula $l=-\max\{a\mid a\in D\}/(b-1)$
+\end_inset
+
+ and 
+\begin_inset Formula $u=-\min\{a\mid a\in D\}/(b-1)$
+\end_inset
+
+.
+ For example,
+ 
+\begin_inset Formula $D=\{-1,0,\dots,b-2\}$
+\end_inset
+
+ satisfies the conditions for all 
+\begin_inset Formula $b\geq3$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+For the statement to make sense,
+ we need 
+\begin_inset Formula $b\geq2$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Obvious.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Take an arbitrary 
+\begin_inset Formula $m\in\mathbb{Z}$
+\end_inset
+
+.
+ If 
+\begin_inset Formula $l\leq m\leq u$
+\end_inset
+
+,
+ we are done.
+ Otherwise,
+ let 
+\begin_inset Formula $q$
+\end_inset
+
+ and 
+\begin_inset Formula $r$
+\end_inset
+
+ be the quotient and remainder of dividing 
+\begin_inset Formula $m$
+\end_inset
+
+ by 
+\begin_inset Formula $b$
+\end_inset
+
+,
+ and let 
+\begin_inset Formula $x\in D$
+\end_inset
+
+ be such that 
+\begin_inset Formula $x\equiv r\pmod b$
+\end_inset
+
+.
+ Then write 
+\begin_inset Formula $x$
+\end_inset
+
+ and,
+ if 
+\begin_inset Formula $k\in\mathbb{Z}$
+\end_inset
+
+ is such that 
+\begin_inset Formula $x=kb+r$
+\end_inset
+
+,
+ write the number 
+\begin_inset Formula $q-k$
+\end_inset
+
+ to the right of the 
+\begin_inset Formula $x$
+\end_inset
+
+ we just wrote by applying this same process.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+We have to prove that this algorithm terminates.
+ First we note that there exists at least an integer between 
+\begin_inset Formula $l$
+\end_inset
+
+ and 
+\begin_inset Formula $u$
+\end_inset
+
+,
+ because there are 
+\begin_inset Formula $b$
+\end_inset
+
+ integers in 
+\begin_inset Formula $D$
+\end_inset
+
+ and so the maximum and minimum must differ by at least 
+\begin_inset Formula $b-1$
+\end_inset
+
+,
+ and so 
+\begin_inset Formula $u-l\geq1$
+\end_inset
+
+.
+ This means that necessarily 
+\begin_inset Formula $l\leq0$
+\end_inset
+
+ and 
+\begin_inset Formula $u\geq0$
+\end_inset
+
+,
+ for if 
+\begin_inset Formula $l>0$
+\end_inset
+
+,
+ then all numbers in 
+\begin_inset Formula $D$
+\end_inset
+
+ are negative,
+ but the integers between 
+\begin_inset Formula $l$
+\end_inset
+
+ and 
+\begin_inset Formula $u$
+\end_inset
+
+ are positive so they couldn't be represented in the given form,
+\begin_inset Formula $\#$
+\end_inset
+
+ and a similar thing would happen if 
+\begin_inset Formula $u<0$
+\end_inset
+
+.
+ Now,
+ in the algorithm above,
+ 
+\begin_inset Formula $q-k=\lfloor\frac{m}{b}\rfloor-k=\frac{m-r}{b}-\frac{x-r}{b}=\frac{m-x}{b}$
+\end_inset
+
+.
+ With this,
+ if 
+\begin_inset Formula $m>u$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $m(b-1)>-\min D$
+\end_inset
+
+,
+ but and therefore
+\begin_inset Formula 
+\[
+m-(q-k)=m-\frac{m-x}{b}=\frac{m(b-1)+x}{b}>\frac{-\min D+\min D}{b}=0,
+\]
+
+\end_inset
+
+so 
+\begin_inset Formula $q-k<m$
+\end_inset
+
+,
+ and 
+\begin_inset Formula 
+\[
+m+(q-k)=\frac{m(b+1)-x}{b}>m-\frac{\max D}{b}\geq m+l,
+\]
+
+\end_inset
+
+so 
+\begin_inset Formula $q-k\geq l$
+\end_inset
+
+.
+ This means that,
+ on each step,
+ 
+\begin_inset Formula $m$
+\end_inset
+
+ is smaller by at least 1,
+ but it doesn't become smaller than 
+\begin_inset Formula $l$
+\end_inset
+
+,
+ so it eventually reaches the interval 
+\begin_inset Formula $[l,u]$
+\end_inset
+
+ in at most 
+\begin_inset Formula $|m-u|$
+\end_inset
+
+ steps.
+ And if 
+\begin_inset Formula $m<l$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $m(b-1)<-\max D$
+\end_inset
+
+,
+ so
+\begin_inset Formula 
+\[
+m-(q-k)=\frac{m(b-1)+x}{b}<\frac{-\max D+\max D}{b}=0,
+\]
+
+\end_inset
+
+so 
+\begin_inset Formula $q-k>m$
+\end_inset
+
+,
+ and
+\begin_inset Formula 
+\[
+m+(q-k)=\frac{m(b+1)-x}{b}<m-\frac{\min D}{b}\leq m+u,
+\]
+
+\end_inset
+
+ so 
+\begin_inset Formula $q-k\leq u$
+\end_inset
+
+,
+ and a similar reasoning applies.
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc21[M22]
+\end_layout
+
+\end_inset
+
+(C.
+ E.
+ Shannon.) Can every real number (positive,
+ negative,
+ or zero) be expressed in a 
+\begin_inset Quotes eld
+\end_inset
+
+balanced decimal
+\begin_inset Quotes erd
+\end_inset
+
+ system,
+ that is,
+ in the form 
+\begin_inset Formula $\sum_{k\leq n}a_{k}10^{k}$
+\end_inset
+
+,
+ for some integer 
+\begin_inset Formula $n$
+\end_inset
+
+ and some sequence 
+\begin_inset Formula $a_{n},a_{n-1},a_{n-2},\dots$
+\end_inset
+
+,
+ where each 
+\begin_inset Formula $a_{k}$
+\end_inset
+
+ is one of the ten numbers 
+\begin_inset Formula $\{-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}\}$
+\end_inset
+
+?
+ (Although zero is not one of the allowed digits,
+ we implicitly assume that 
+\begin_inset Formula $a_{n+1},a_{n+2},\dots$
+\end_inset
+
+ are zero.) Find all representations of zero in this number system,
+ and find all representations of unity.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Yes,
+ we can do something similar to the construction of balanced ternary.
+ First,
+ we add 
+\begin_inset Formula $5\cdot10^{n+1}$
+\end_inset
+
+ to the number,
+ and then we subtract 
+\begin_inset Formula $4\frac{1}{2}$
+\end_inset
+
+ from each digit from the 
+\begin_inset Formula $(n+1)$
+\end_inset
+
+st to the right.
+\end_layout
+
+\begin_layout Standard
+For a sum in the given form to be 0,
+ 
+\begin_inset Formula $a_{n}10^{n}$
+\end_inset
+
+ must equal 
+\begin_inset Formula $-\sum_{k<n}a_{k}10^{k}$
+\end_inset
+
+.
+ The biggest value we can write as 
+\begin_inset Formula $\sum_{k<n}a_{k}10^{k}$
+\end_inset
+
+ is 
+\begin_inset Formula $5\cdot10^{n-1}=10^{n}/2$
+\end_inset
+
+,
+ which we can only reach if all those 
+\begin_inset Formula $a_{k}=4\frac{1}{2}$
+\end_inset
+
+,
+ and the smallest is 
+\begin_inset Formula $-10^{n}/2$
+\end_inset
+
+,
+ where all the 
+\begin_inset Formula $a_{k}=-4\frac{1}{2}$
+\end_inset
+
+,
+ so the representations are 
+\begin_inset Quotes eld
+\end_inset
+
+
+\begin_inset Formula $-\frac{1}{2},4\frac{1}{2},4\frac{1}{2},4\frac{1}{2},\dots$
+\end_inset
+
+
+\begin_inset Quotes erd
+\end_inset
+
+ and 
+\begin_inset Quotes eld
+\end_inset
+
+
+\begin_inset Formula $\frac{1}{2},-4\frac{1}{2},-4\frac{1}{2},-4\frac{1}{2},\dots$
+\end_inset
+
+
+\begin_inset Quotes erd
+\end_inset
+
+,
+ with the decimal point in any arbitrary position.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+begin{sloppypar}
+\end_layout
+
+\end_inset
+
+To get one,
+ we need 
+\begin_inset Formula $\frac{1}{2}+\frac{1}{2}$
+\end_inset
+
+ or 
+\begin_inset Formula $1\frac{1}{2}-\frac{1}{2}$
+\end_inset
+
+,
+ so either 
+\begin_inset Quotes eld
+\end_inset
+
+
+\begin_inset Formula $\frac{1}{2};4\frac{1}{2},\dots,4\frac{1}{2},\dots$
+\end_inset
+
+
+\begin_inset Quotes erd
+\end_inset
+
+ or 
+\begin_inset Quotes eld
+\end_inset
+
+
+\begin_inset Formula $1\frac{1}{2};-4\frac{1}{2},\dots,-4\frac{1}{2},\dots$
+\end_inset
+
+
+\begin_inset Quotes erd
+\end_inset
+
+,
+ or 
+\begin_inset Quotes eld
+\end_inset
+
+
+\begin_inset Formula $\frac{1}{2},-4\frac{1}{2},\dots,-4\frac{1}{2},-3\frac{1}{2},-4\frac{1}{2},\dots,-4\frac{1}{2},\dots$
+\end_inset
+
+
+\begin_inset Quotes erd
+\end_inset
+
+ or 
+\begin_inset Quotes eld
+\end_inset
+
+
+\begin_inset Formula $\frac{1}{2},-4\frac{1}{2},\dots,-4\frac{1}{2};4\frac{1}{2},\dots,4\frac{1}{2},\dots$
+\end_inset
+
+
+\begin_inset Quotes erd
+\end_inset
+
+,
+ which stem from representing 
+\begin_inset Formula $\frac{1}{2}$
+\end_inset
+
+ and 
+\begin_inset Formula $1\frac{1}{2}$
+\end_inset
+
+ in a way similar to the one used to represent the zero above.
+ Here the semicolon represents the radix point.
+ The most significant digit must be positive and to the left of the radix point,
+ and we can use this fact to show that these are all the ways that the number 1 can be represented in this system.
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+end{sloppypar}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc28[M24]
+\end_layout
+
+\end_inset
+
+Show that every nonzero complex number of the form 
+\begin_inset Formula $a+b\text{i}$
+\end_inset
+
+ where 
+\begin_inset Formula $a$
+\end_inset
+
+ and 
+\begin_inset Formula $b$
+\end_inset
+
+ are integers has a unique 
+\begin_inset Quotes eld
+\end_inset
+
+revolving binary representation
+\begin_inset Quotes erd
+\end_inset
+
+
+\begin_inset Formula 
+\[
+(1+\text{i})^{e_{0}}+\text{i}(1+\text{i})^{e_{1}}-(1+\text{i})^{e_{2}}-\text{i}(1+\text{i})^{e_{3}}+\dots+\text{i}^{t}(1+\text{i})^{e_{t}},
+\]
+
+\end_inset
+
+where 
+\begin_inset Formula $e_{0}<e_{1}<\dots<e_{t}$
+\end_inset
+
+.
+ (Compare with exercise 27.)
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+First we show that such representation exists by providing an algorithm for getting it from a number 
+\begin_inset Formula $c\in\mathbb{Z}+\text{i}\mathbb{Z}$
+\end_inset
+
+:
+\end_layout
+
+\begin_layout Enumerate
+[Initialize.] Set 
+\begin_inset Formula $s\gets0$
+\end_inset
+
+ and 
+\begin_inset Formula $e\gets0$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset CommandInset label
+LatexCommand label
+name "enu:e4128b"
+
+\end_inset
+
+[Case 
+\begin_inset Formula $(1+\text{i})^{0}$
+\end_inset
+
+.] If 
+\begin_inset Formula $\text{Re}c$
+\end_inset
+
+ is odd and 
+\begin_inset Formula $\text{Im}c$
+\end_inset
+
+ is even,
+ or vice versa,
+ write down 
+\begin_inset Formula $\text{i}^{s}(1+\text{i})^{e}$
+\end_inset
+
+ and set 
+\begin_inset Formula $s\gets s+1$
+\end_inset
+
+ and 
+\begin_inset Formula $c\gets-\text{i}(c-1)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset CommandInset label
+LatexCommand label
+name "enu:e4128c"
+
+\end_inset
+
+[Case 
+\begin_inset Formula $(1+\text{i})^{1}$
+\end_inset
+
+.] If 
+\begin_inset Formula $\text{Re}c$
+\end_inset
+
+ is odd [if,
+ and only if,
+ 
+\begin_inset Formula $\text{Im}c$
+\end_inset
+
+ is odd,] write down 
+\begin_inset Formula $\text{i}^{s}(1+\text{i})^{e+1}$
+\end_inset
+
+ and set 
+\begin_inset Formula $s\gets s+1$
+\end_inset
+
+ and 
+\begin_inset Formula $c\gets-\text{i}(c-1-\text{i})$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset CommandInset label
+LatexCommand label
+name "enu:e4128d"
+
+\end_inset
+
+[Iterate.] If 
+\begin_inset Formula $c\neq0$
+\end_inset
+
+,
+ set 
+\begin_inset Formula $e\gets e+2$
+\end_inset
+
+ and 
+\begin_inset Formula $c\gets\frac{c}{2\text{i}}$
+\end_inset
+
+ and go back to step 
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "enu:e4128b"
+plural "false"
+caps "false"
+noprefix "false"
+nolink "false"
+
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+The algorithm always maintains the invariant that 
+\begin_inset Formula $c_{0}=w+\text{i}^{s}(1+\text{i})^{e}c$
+\end_inset
+
+,
+ where 
+\begin_inset Formula $c_{0}$
+\end_inset
+
+ is the original value of 
+\begin_inset Formula $c$
+\end_inset
+
+ and 
+\begin_inset Formula $w$
+\end_inset
+
+ is the sum of the terms that have been written,
+ so when it finishes,
+ 
+\begin_inset Formula $w=c_{0}$
+\end_inset
+
+,
+ and it's trivial to see that 
+\begin_inset Formula $w$
+\end_inset
+
+ is a revolving binary representation.
+ To see that the algorithm terminates,
+ we see that,
+ after each iteration,
+ 
+\begin_inset Formula $c$
+\end_inset
+
+ has a smaller magnitude except if originally 
+\begin_inset Formula $c=-1,-\text{i},-1-\text{i}$
+\end_inset
+
+,
+ but in these cases the iteration after that will lower the magnitude of 
+\begin_inset Formula $c$
+\end_inset
+
+,
+ preventing an infinite loop:
+\begin_inset Formula 
+\begin{align*}
+-1 & \overset{\eqref{enu:e4128b}}{\to}2\text{i}\overset{\eqref{enu:e4128d}}{\to}1, & -\text{i} & \overset{\eqref{enu:e4128b}}{\to}\text{i}-1\overset{\eqref{enu:e4128c}}{\to}2\text{i}\overset{\eqref{enu:e4128d}}{\to}1, & -1-\text{i} & \overset{\eqref{enu:e4128c}}{\to}2\text{i}-2\overset{\eqref{enu:e4128d}}{\to}\text{i}+1.
+\end{align*}
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+For the uniqueness,
+ let 
+\begin_inset Formula $\sum_{k=0}^{n}\text{i}^{k}(1+\text{i})^{e_{k}}=\sum_{j=0}^{m}\text{i}^{j}(1+\text{i})^{f_{j}}$
+\end_inset
+
+ (
+\begin_inset Formula $n,m,e_{k},f_{j}\in\mathbb{N}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $e_{0}<\dots<e_{n}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $f_{0}<\dots<f_{m}$
+\end_inset
+
+) be two different representations of the same number,
+ and let 
+\begin_inset Formula $s\leq m,n$
+\end_inset
+
+ be the first index where they differ (let's say 
+\begin_inset Formula $e_{s}<f_{s}$
+\end_inset
+
+).
+ Then we may remove all terms before 
+\begin_inset Formula $s$
+\end_inset
+
+ in both representations and divide each remaining term by 
+\begin_inset Formula $\text{i}^{s}(1+\text{i})^{e_{s}}$
+\end_inset
+
+.
+ But then,
+ the second representation is a multiple of 
+\begin_inset Formula $(1+\text{i})^{\min\{e_{s}+1,f_{s}\}}$
+\end_inset
+
+ in 
+\begin_inset Formula $\mathbb{Z}+\text{i}\mathbb{Z}$
+\end_inset
+
+ but the first one isn't.
+\begin_inset Formula $\#$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc34[22]
+\end_layout
+
+\end_inset
+
+(G.
+ W.
+ Reitweisner,
+ 1960.) Explain how to represent a given integer 
+\begin_inset Formula $n$
+\end_inset
+
+ in the form 
+\begin_inset Formula $(\dots a_{2}a_{1}a_{0})_{2}$
+\end_inset
+
+,
+ where each 
+\begin_inset Formula $a_{j}$
+\end_inset
+
+ is 
+\begin_inset Formula $-1$
+\end_inset
+
+,
+ 0,
+ or 1,
+ using the fewest nonzero digits.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+If 
+\begin_inset Formula $n=0$
+\end_inset
+
+,
+ we just write 0.
+ If 
+\begin_inset Formula $n>0$
+\end_inset
+
+,
+ we take 
+\begin_inset Formula $k\in\mathbb{N}$
+\end_inset
+
+ such that 
+\begin_inset Formula $|2^{k}-n|$
+\end_inset
+
+ is minimum,
+ write a 1 at position 
+\begin_inset Formula $k$
+\end_inset
+
+,
+ and then write 
+\begin_inset Formula $n-2^{k}$
+\end_inset
+
+ on the 
+\begin_inset Formula $k$
+\end_inset
+
+ positions to the right.
+ If 
+\begin_inset Formula $n<0$
+\end_inset
+
+,
+ we do the same except that first we write 
+\begin_inset Formula $\overline{1}$
+\end_inset
+
+ instead of 1.
+\end_layout
+
+\begin_layout Standard
+Now we prove that this in fact results in the representation fewest number of nonzero digits.
+ We only need to prove it for positive 
+\begin_inset Formula $n$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Now,
+ if 
+\begin_inset Formula $n=2^{k}$
+\end_inset
+
+ or 
+\begin_inset Formula $3\cdot2^{k}$
+\end_inset
+
+ for some 
+\begin_inset Formula $k\in\mathbb{N}$
+\end_inset
+
+,
+ the statement is trivial.
+ Otherwise,
+ if 
+\begin_inset Formula $2^{k}<n<2^{k+1}$
+\end_inset
+
+ for some 
+\begin_inset Formula $k\in\mathbb{N}$
+\end_inset
+
+,
+ we operate by induction.
+ First note that,
+ for such 
+\begin_inset Formula $n$
+\end_inset
+
+,
+ 
+\begin_inset Formula $k\geq2$
+\end_inset
+
+,
+ and that all possible representations start with a 1 at position 
+\begin_inset Formula $k$
+\end_inset
+
+ or 
+\begin_inset Formula $k+1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+If 
+\begin_inset Formula $n<3\cdot2^{k-1}$
+\end_inset
+
+,
+ let 
+\begin_inset Formula $\sigma(s)$
+\end_inset
+
+ be the minimum number of nonzero digits in a representation of 
+\begin_inset Formula $s$
+\end_inset
+
+,
+ then if we start with a 1 at position 
+\begin_inset Formula $k$
+\end_inset
+
+ we would have a minimum of 
+\begin_inset Formula $1+\sigma(n-2^{k})$
+\end_inset
+
+ nonzero digits,
+ whereas if we start at position 
+\begin_inset Formula $k+1$
+\end_inset
+
+ we would have a minimum of 
+\begin_inset Formula $1+\sigma(2^{k+1}-n)$
+\end_inset
+
+.
+ Let 
+\begin_inset Formula $t\coloneqq2^{k+1}-n>2^{k-1}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $t$
+\end_inset
+
+ would need to have its most significant digit in position 
+\begin_inset Formula $k$
+\end_inset
+
+ or 
+\begin_inset Formula $k-1$
+\end_inset
+
+,
+ but any representation of 
+\begin_inset Formula $t$
+\end_inset
+
+ that starts at position 
+\begin_inset Formula $k$
+\end_inset
+
+ can be converted into one of 
+\begin_inset Formula $2^{k}-n$
+\end_inset
+
+ by removing the 1 at that position,
+ and any one starting at position 
+\begin_inset Formula $k-1$
+\end_inset
+
+ can be converted into one of 
+\begin_inset Formula $2^{k}-n$
+\end_inset
+
+ by swapping the sign in that position,
+ so in general 
+\begin_inset Formula $\sigma(t)=\sigma(2^{k+1}-n)\geq\sigma(2^{k}-n)=\sigma(n-2^{k})$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+A similar argument shows that,
+ if 
+\begin_inset Formula $n>3\cdot2^{k-1}$
+\end_inset
+
+,
+ then 
+\begin_inset Formula $\sigma(n-2^{k})\geq\sigma(2^{k+1}-n)$
+\end_inset
+
+.
+\end_layout
+
+\end_body
+\end_document