diff options
| -rw-r--r-- | 4.1.lyx | 1897 | ||||
| -rw-r--r-- | index.lyx | 20 |
2 files changed, 1901 insertions, 16 deletions
@@ -0,0 +1,1897 @@ +#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 +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. +\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 @@ -2221,22 +2221,10 @@ Positional Number Systems \end_layout \begin_layout Standard -\begin_inset Note Note -status open - -\begin_layout Plain Layout -16+4; - 2, - 5, - 8, - 9, - 13, - 19, - 21, - 28, - 34 (2:15) -> 10d, - -2/3 -\end_layout +\begin_inset CommandInset include +LatexCommand input +filename "4.1.lyx" +literal "false" \end_inset |