Changed layout for more manageable volumes

1 files changed, 0 insertions, 1204 deletions

diff --git a/3.1.lyx b/3.1.lyx
deleted file mode 100644
index 81d7d26..0000000
--- a/3.1.lyx
+++ /dev/null
@@ -1,1204 +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
-rexerc1[20]
-\end_layout
-
-\end_inset
-
-Suppose that you wish to obtain a decimal digit at random,
- not using a computer.
- Which of the following methods would be suitable?
-\end_layout
-
-\begin_layout Enumerate
-Open a telephone directory to a random place by sticking your finger in it somewhere,
- and use the units digit of the first number found on the selected page.
-\end_layout
-
-\begin_layout Enumerate
-Same as (a),
- but use the units digit of the 
-\emph on
-page
-\emph default
- number.
-\end_layout
-
-\begin_layout Enumerate
-Roll a die that is in the shape of a regular icosahedron,
- whose twenty faces have been labeled with the digits 0,
- 0,
- 1,
- 1,
- ...,
- 9,
- 9.
- Use the digit that appears on the top,
- when the die comes to rest.
- (A felt-covered table with a hard surface is recommended for rolling dice.)
-\end_layout
-
-\begin_layout Enumerate
-Expose a geiger counter to a source of radioactivity for one minute (shielding yourself) and use the units digit of the resulting count.
- Assume that the geiger counter displays the number of counts in decimal notation,
- and that the count is initially zero.
-\end_layout
-
-\begin_layout Enumerate
-Glance at your wristwatch;
- and if the position of the second-hand is between 
-\begin_inset Formula $6n$
-\end_inset
-
- and 
-\begin_inset Formula $6(n+1)$
-\end_inset
-
- seconds,
- choose the digit 
-\begin_inset Formula $n$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Enumerate
-Ask a friend to think of a random digit,
- and use the digit he names.
-\end_layout
-
-\begin_layout Enumerate
-Ask an enemy to think of a random digit,
- and use the digit he names.
-\end_layout
-
-\begin_layout Enumerate
-Assume that 10 horses are entered in a race and that you know nothing whatever about their qualifications.
- Assign to these horses the digits 0 to 9,
- in arbitrary fashion,
- and after the race use the winner's digit.
-\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
-This would work for a typical phone book.
- It wouldn't work if the book has,
- say,
- entries ordered by number with a fixed number of entries per page that is a multiple of 2 or 5.
- And,
- according to the official solution,
- in some places people can choose phone numbers (presumably in the US where Knuth lives) so it wouldn't work there as people would tend to choose round numbers.
-\end_layout
-
-\begin_layout Enumerate
-This would be suitable,
- although some adjustment would have to be made to account for the fact that left pages would have even numbers and right pages would have round numbers (say,
- we could take the even number and divide it by two) and to avoid the last few pages if the total number is not a multiple of 20.
-\end_layout
-
-\begin_layout Enumerate
-This would work very well.
-\end_layout
-
-\begin_layout Enumerate
-This would work well assuming there are several digits between the most significant one and the units.
-\end_layout
-
-\begin_layout Enumerate
-This would work assuming you only have to do it once at a time and not at a specific time.
-\end_layout
-
-\begin_layout Enumerate
-This wouldn't work,
- as humans are not good at mentally generating random numbers.
-\end_layout
-
-\begin_layout Enumerate
-This definitely wouldn't work,
- as the enemy would probably be compelled to choose the number strategically instead of randomly.
-\end_layout
-
-\begin_layout Enumerate
-This could work,
- although it would be time consuming.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-exerc3[10]
-\end_layout
-
-\end_inset
-
-What number follows 1010101010 in the middle-square method?
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-
-\begin_inset Formula $1010101010^{2}=1020304050403020100$
-\end_inset
-
-,
- so the next number would be 3040504030.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc6[M21]
-\end_layout
-
-\end_inset
-
-Suppose that we want to generate a sequence of integers 
-\begin_inset Formula $X_{0},X_{1},X_{2},\dots$
-\end_inset
-
-,
- in the range 
-\begin_inset Formula $0\leq X_{n}<m$
-\end_inset
-
-.
- Let 
-\begin_inset Formula $f(x)$
-\end_inset
-
- be any function such that 
-\begin_inset Formula $0\leq x<m$
-\end_inset
-
- implies 
-\begin_inset Formula $0\leq f(x)<m$
-\end_inset
-
-.
- Consider a sequence formed by the rule 
-\begin_inset Formula $X_{n+1}=f(X_{n})$
-\end_inset
-
-.
- (Examples are the middle-square method and Algorithm K.)
-\end_layout
-
-\begin_layout Enumerate
-Show that the sequence is ultimately periodic,
- in the sense that there exist numbers 
-\begin_inset Formula $\lambda$
-\end_inset
-
- and 
-\begin_inset Formula $\mu$
-\end_inset
-
- for which the values
-\begin_inset Formula 
-\[
-X_{0},X_{1},\dots,X_{\mu},\dots,X_{\mu+\lambda-1}
-\]
-
-\end_inset
-
-are distinct,
- but 
-\begin_inset Formula $X_{n+\lambda}=X_{n}$
-\end_inset
-
- when 
-\begin_inset Formula $n\geq\mu$
-\end_inset
-
-.
- Find the maximum and minimum possible values of 
-\begin_inset Formula $\mu$
-\end_inset
-
- and 
-\begin_inset Formula $\lambda$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Enumerate
-\begin_inset CommandInset label
-LatexCommand label
-name "enu:e316b"
-
-\end_inset
-
-(R.
- W.
- Floyd.) Show that there exists an 
-\begin_inset Formula $n>0$
-\end_inset
-
- such that 
-\begin_inset Formula $X_{n}=X_{2n}$
-\end_inset
-
-;
- and the smallest such value of 
-\begin_inset Formula $n$
-\end_inset
-
- lies in the range 
-\begin_inset Formula $\mu\le n\leq\mu+\lambda$
-\end_inset
-
-.
- Furthermore the value of 
-\begin_inset Formula $X_{n}$
-\end_inset
-
- is unique in the sense that if 
-\begin_inset Formula $X_{n}=X_{2n}$
-\end_inset
-
- and 
-\begin_inset Formula $X_{r}=X_{2r}$
-\end_inset
-
-,
- then 
-\begin_inset Formula $X_{r}=X_{n}$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Enumerate
-Use the idea of part 
-\begin_inset CommandInset ref
-LatexCommand ref
-reference "enu:e316b"
-plural "false"
-caps "false"
-noprefix "false"
-nolink "false"
-
-\end_inset
-
- to design an algorithm that calculates 
-\begin_inset Formula $\mu$
-\end_inset
-
- and 
-\begin_inset Formula $\lambda$
-\end_inset
-
- for any given function 
-\begin_inset Formula $f$
-\end_inset
-
- and any given 
-\begin_inset Formula $X_{0}$
-\end_inset
-
-,
- using only 
-\begin_inset Formula $O(\mu+\lambda)$
-\end_inset
-
- steps and only a bounded number of memory locations.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-Assume 
-\begin_inset Formula $f:\mathbb{Z}_{m}\to\mathbb{Z}_{m}$
-\end_inset
-
-,
- as otherwise the statements below are not necessarily true (e.g.
- if 
-\begin_inset Formula $f:\mathbb{R}\to\mathbb{R}$
-\end_inset
-
-,
- 
-\begin_inset Formula $f(x)\coloneqq\frac{x}{2}$
-\end_inset
-
-,
- and 
-\begin_inset Formula $X_{0}=\frac{m}{2}$
-\end_inset
-
-).
-\end_layout
-
-\begin_layout Enumerate
-Require that 
-\begin_inset Formula $\mu\in\mathbb{N}$
-\end_inset
-
- and 
-\begin_inset Formula $\lambda\in\mathbb{N}^{*}$
-\end_inset
-
-,
- as otherwise it is unclear what is meant and,
- in particular,
- the statement is obviously true when 
-\begin_inset Formula $\mu\in\mathbb{N}$
-\end_inset
-
- and 
-\begin_inset Formula $\lambda=0$
-\end_inset
-
-.
- Now,
- since 
-\begin_inset Formula $\{X_{0},\dots,X_{m}\}\subseteq\{0,\dots,m-1\}$
-\end_inset
-
-,
- then 
-\begin_inset Formula $|\{X_{0},\dots,X_{m}\}|\leq m$
-\end_inset
-
- and there must be integers 
-\begin_inset Formula $i$
-\end_inset
-
- and 
-\begin_inset Formula $j$
-\end_inset
-
-,
- 
-\begin_inset Formula $0\leq i<j\leq m$
-\end_inset
-
-,
- such that 
-\begin_inset Formula $X_{i}=X_{j}$
-\end_inset
-
-.
- We choose 
-\begin_inset Formula $i$
-\end_inset
-
- and 
-\begin_inset Formula $j$
-\end_inset
-
- such that 
-\begin_inset Formula $j$
-\end_inset
-
- is minimum,
- which ensures that 
-\begin_inset Formula $X_{0},\dots,X_{j-1}$
-\end_inset
-
- are distinct and uniquely determines 
-\begin_inset Formula $i$
-\end_inset
-
-,
- and we set 
-\begin_inset Formula $\mu\coloneqq i$
-\end_inset
-
- and 
-\begin_inset Formula $\lambda\coloneqq j-i$
-\end_inset
-
-;
- then 
-\begin_inset Formula $X_{0},\dots,X_{\mu+\lambda-1=j-1}$
-\end_inset
-
- are all distinct and,
- for 
-\begin_inset Formula $n\geq\mu$
-\end_inset
-
-,
-\begin_inset Formula 
-\[
-X_{n+\lambda}=X_{n-i+j}=f^{n-i}(X_{j})=f^{n-i}(X_{i})=X_{n}.
-\]
-
-\end_inset
-
-It's easy to check that these values are unique:
- 
-\begin_inset Formula $\mu+\lambda$
-\end_inset
-
- must be the first value such that 
-\begin_inset Formula $X_{\mu+\lambda}$
-\end_inset
-
- equals some other value earlier in the sequence,
- and 
-\begin_inset Formula $\mu$
-\end_inset
-
- must be the only value less than 
-\begin_inset Formula $\mu+\lambda$
-\end_inset
-
- such that 
-\begin_inset Formula $X_{\mu}=X_{\mu+\lambda}$
-\end_inset
-
-.
-\end_layout
-
-\begin_deeper
-\begin_layout Standard
-As for the maximum and minimum,
- since 
-\begin_inset Formula $0\leq i<j\leq m$
-\end_inset
-
-,
- we have 
-\begin_inset Formula $0\leq\mu\leq m-1$
-\end_inset
-
- and 
-\begin_inset Formula $1\leq\lambda\leq m$
-\end_inset
-
-.
- These bounds can be reached:
- when 
-\begin_inset Formula $f$
-\end_inset
-
- is the identity,
- 
-\begin_inset Formula $\mu=0$
-\end_inset
-
- and 
-\begin_inset Formula $\lambda=1$
-\end_inset
-
-;
- when 
-\begin_inset Formula $f(x)=(x+1)\bmod m$
-\end_inset
-
-,
- 
-\begin_inset Formula $\lambda=m$
-\end_inset
-
-,
- and when 
-\begin_inset Formula $f(x)=\max\{0,x-1\}$
-\end_inset
-
- and 
-\begin_inset Formula $X_{0}=m-1$
-\end_inset
-
-,
- 
-\begin_inset Formula $\mu=m-1$
-\end_inset
-
-.
-\end_layout
-
-\end_deeper
-\begin_layout Enumerate
-Let 
-\begin_inset Formula $k\coloneqq\lceil\frac{\mu}{\lambda}\rceil$
-\end_inset
-
- and 
-\begin_inset Formula $n\coloneqq k\lambda$
-\end_inset
-
-,
- then 
-\begin_inset Formula $\frac{\mu}{\lambda}\leq k\leq\frac{\mu}{\lambda}+1$
-\end_inset
-
- and therefore 
-\begin_inset Formula $\mu\leq n\leq\mu+\lambda$
-\end_inset
-
-,
- and 
-\begin_inset Formula $X_{n}=X_{n+\lambda}=X_{n+2\lambda}=\dots=X_{n+k\lambda=2n}$
-\end_inset
-
-.
- For the uniqueness,
- let 
-\begin_inset Formula $r>0$
-\end_inset
-
- be such that 
-\begin_inset Formula $X_{r}=X_{2r}$
-\end_inset
-
-,
- so necessarily 
-\begin_inset Formula $2r\geq\mu+\lambda$
-\end_inset
-
-.
- We note that,
- for any 
-\begin_inset Formula $s\geq\mu$
-\end_inset
-
-,
- by induction,
- 
-\begin_inset Formula $X_{s}=X_{s-\lfloor\frac{s-\mu}{\lambda}\rfloor\lambda}=X_{\mu+((s-\mu)\bmod\lambda)}$
-\end_inset
-
-,
- and we call 
-\begin_inset Formula $R(s)\coloneqq\mu+((s-\mu)\bmod\lambda)\in\{\mu,\dots,\mu+\lambda-1\}$
-\end_inset
-
-.
- With this,
- 
-\begin_inset Formula $X_{R(2r)}=X_{2r}=X_{r}$
-\end_inset
-
-,
- so either 
-\begin_inset Formula $r=R(2r)$
-\end_inset
-
- or 
-\begin_inset Formula $r\geq\mu+\lambda$
-\end_inset
-
-;
- in any case 
-\begin_inset Formula $r\geq\mu$
-\end_inset
-
- and 
-\begin_inset Formula $X_{R(2r)}=X_{R(r)}$
-\end_inset
-
-.
- This means 
-\begin_inset Formula $R(2r)=R(r)$
-\end_inset
-
-,
- so 
-\begin_inset Formula $r\equiv0\mod{\lambda}$
-\end_inset
-
- and 
-\begin_inset Formula $R(r)=\mu+(-\mu\bmod\lambda)\equiv0\bmod\lambda$
-\end_inset
-
-,
- so 
-\begin_inset Formula $R(r)$
-\end_inset
-
- is unique and 
-\begin_inset Formula $X_{r}=X_{R(r)}=X_{R(n)}=X_{n}$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Enumerate
-First we set 
-\begin_inset Formula $a,b\gets X_{0}$
-\end_inset
-
- and then repeatedly set 
-\begin_inset Formula $a\gets f(a)$
-\end_inset
-
- and 
-\begin_inset Formula $b\gets f^{2}(b)$
-\end_inset
-
- until 
-\begin_inset Formula $a=b$
-\end_inset
-
-;
- the number of times we do this operation is 
-\begin_inset Formula $n$
-\end_inset
-
-,
- and in the end 
-\begin_inset Formula $a=X_{n}$
-\end_inset
-
-.
- Then we set 
-\begin_inset Formula $b\gets a$
-\end_inset
-
- and repeat 
-\begin_inset Formula $b\gets f(b)$
-\end_inset
-
- until 
-\begin_inset Formula $b=a$
-\end_inset
-
-;
- the number of times we do this operation is 
-\begin_inset Formula $\lambda$
-\end_inset
-
-.
- Finally,
- since 
-\begin_inset Formula $a$
-\end_inset
-
- is a multiple of 
-\begin_inset Formula $\lambda$
-\end_inset
-
-,
- 
-\begin_inset Formula $X_{\mu}=X_{\mu+n}$
-\end_inset
-
-,
- so we set 
-\begin_inset Formula $b\gets X_{0}$
-\end_inset
-
- and repeat 
-\begin_inset Formula $b\gets f(b)$
-\end_inset
-
- and 
-\begin_inset Formula $a\gets f(a)$
-\end_inset
-
- until 
-\begin_inset Formula $a=b$
-\end_inset
-
-;
- the number of times we do this operation is 
-\begin_inset Formula $\mu$
-\end_inset
-
-.
- In total this uses two slots of memory and runs in time 
-\begin_inset Formula $O(n)+O(\lambda)+O(\mu)=O(\mu+\lambda)$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-rexerc7[M21]
-\end_layout
-
-\end_inset
-
-(R.
- P.
- Brent,
- 1977.) Let 
-\begin_inset Formula $\ell(n)$
-\end_inset
-
- be the greatest power of 2 that is less than or equal to 
-\begin_inset Formula $n$
-\end_inset
-
-;
- thus,
- for example,
- 
-\begin_inset Formula $\ell(15)=8$
-\end_inset
-
- and 
-\begin_inset Formula $\ell(\ell(n))=\ell(n)$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Enumerate
-Show that,
- in terms of the notation in exercise 6,
- there exists an 
-\begin_inset Formula $n>0$
-\end_inset
-
- such that 
-\begin_inset Formula $X_{n}=X_{\ell(n)-1}$
-\end_inset
-
-.
- Find a formula that expresses the least such 
-\begin_inset Formula $n$
-\end_inset
-
- in terms of the periodicity numbers 
-\begin_inset Formula $\mu$
-\end_inset
-
- and 
-\begin_inset Formula $\lambda$
-\end_inset
-
-.
-\end_layout
-
-\begin_layout Enumerate
-Apply this result to design an algorithm that can be used in conjunction with any random number generator of the type 
-\begin_inset Formula $X_{n+1}=f(X_{n})$
-\end_inset
-
-,
- to prevent it from cycling indefinitely.
- Your algorithm should calculate the period length 
-\begin_inset Formula $\lambda$
-\end_inset
-
-,
- and it should only use a small amount of memory space—
-you must not simply store all the computed sequence values!
-\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
-For sufficiently large 
-\begin_inset Formula $r$
-\end_inset
-
-,
- 
-\begin_inset Formula $n\coloneqq2^{r}-1+\lambda<2^{r+1}$
-\end_inset
-
- and then 
-\begin_inset Formula $X_{\ell(n)-1}=X_{2^{r}-1}=X_{n}$
-\end_inset
-
-,
- and it's easy to convince ourselves that all such 
-\begin_inset Formula $n$
-\end_inset
-
- are of the form 
-\begin_inset Formula $2^{r}-1+k\lambda$
-\end_inset
-
- with 
-\begin_inset Formula $r\in\mathbb{N}$
-\end_inset
-
-,
- 
-\begin_inset Formula $k\in\mathbb{N}^{*}$
-\end_inset
-
-,
- 
-\begin_inset Formula $k\lambda-1<2^{r}$
-\end_inset
-
-,
- and 
-\begin_inset Formula $2^{r}-1\geq\mu$
-\end_inset
-
-.
- The minimum value,
- then,
- happens with 
-\begin_inset Formula $k=1$
-\end_inset
-
- and 
-\begin_inset Formula $2^{r}$
-\end_inset
-
- is the minimum such that 
-\begin_inset Formula $\lambda,\mu+1\leq2^{r}$
-\end_inset
-
-,
- so if 
-\begin_inset Formula $u(n)$
-\end_inset
-
- is the lowest power of 2 that is greater than or equal to 
-\begin_inset Formula $n$
-\end_inset
-
-,
- then
-\begin_inset Formula 
-\[
-n=u(\max\{\lambda,\mu+1\})+\lambda-1.
-\]
-
-\end_inset
-
-
-\end_layout
-
-\begin_layout Enumerate
-We set 
-\begin_inset Formula $a\gets b\gets X_{0}$
-\end_inset
-
- and 
-\begin_inset Formula $r\gets0$
-\end_inset
-
-.
- Then repeat 
-\begin_inset Formula $b\gets f(b)$
-\end_inset
-
- up to 
-\begin_inset Formula $2^{r}$
-\end_inset
-
- times;
- if at any point 
-\begin_inset Formula $b=a$
-\end_inset
-
-,
- terminate with 
-\begin_inset Formula $\lambda$
-\end_inset
-
- equal to the number of times that 
-\begin_inset Formula $b\gets f(b)$
-\end_inset
-
- has been run in this iteration;
- otherwise set 
-\begin_inset Formula $a\gets b$
-\end_inset
-
-,
- 
-\begin_inset Formula $r\gets r+1$
-\end_inset
-
-,
- and repeat this step.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-exerc16[15]
-\end_layout
-
-\end_inset
-
-A sequence generated as in exercise 6 must begin to repeat after at most 
-\begin_inset Formula $m$
-\end_inset
-
- values have been generated.
- Suppose we generalize the method so that 
-\begin_inset Formula $X_{n+1}$
-\end_inset
-
- depends on 
-\begin_inset Formula $X_{n-1}$
-\end_inset
-
- as well as on 
-\begin_inset Formula $X_{n}$
-\end_inset
-
-;
- formally,
- let 
-\begin_inset Formula $f(x,y)$
-\end_inset
-
- be a function such that 
-\begin_inset Formula $0\leq x,y<m$
-\end_inset
-
- implies 
-\begin_inset Formula $0\leq f(x,y)<m$
-\end_inset
-
-.
- The sequence is constructed by selecting 
-\begin_inset Formula $X_{0}$
-\end_inset
-
- and 
-\begin_inset Formula $X_{1}$
-\end_inset
-
- arbitrarily,
- and then letting
-\begin_inset Formula 
-\begin{align*}
-X_{n+1} & =f(X_{n},X_{n-1}), & \text{for }n & >0.
-\end{align*}
-
-\end_inset
-
-What is the maximum period conceivably attainable in this case?
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-See exercise 17.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-exerc17[10]
-\end_layout
-
-\end_inset
-
-Generalize the situation in the previous exercise so that 
-\begin_inset Formula $X_{n+1}$
-\end_inset
-
- depends on the preceding 
-\begin_inset Formula $k$
-\end_inset
-
- values of the sequence.
-\end_layout
-
-\begin_layout Standard
-\begin_inset ERT
-status open
-
-\begin_layout Plain Layout
-
-
-\backslash
-answer 
-\end_layout
-
-\end_inset
-
-The maximum conceivable would be 
-\begin_inset Formula $m^{k}$
-\end_inset
-
-.
- Why this is always attainable is not at all obvious.
-\end_layout
-
-\end_body
-\end_document