diff options
Diffstat (limited to '4.1.lyx')
| -rw-r--r-- | 4.1.lyx | 1897 |
1 files changed, 0 insertions, 1897 deletions
diff --git a/4.1.lyx b/4.1.lyx deleted file mode 100644 index aba30d7..0000000 --- a/4.1.lyx +++ /dev/null @@ -1,1897 +0,0 @@ -#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 |