path: root/vol1/2.3.4.3.lyx

#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 Note Note
status open

\begin_layout Plain Layout
TODO 1,
 3,
 6 (2pp.,
 0:46)
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc1[M10]
\end_layout

\end_inset

The text refers to a set 
\begin_inset Formula $S$
\end_inset

 containing finite sequences of positive integers,
 and states that this set is 
\begin_inset Quotes eld
\end_inset

essentially an oriented tree.
\begin_inset Quotes erd
\end_inset

 What is the root of this oriented tree,
 and what are the arcs?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

The vertices are the elements of 
\begin_inset Formula $S$
\end_inset

,
 the root is 
\begin_inset Formula $\emptyset$
\end_inset

,
 and the arcs go from 
\begin_inset Formula $(x_{1},\dots,x_{n})$
\end_inset

 to 
\begin_inset Formula $(x_{1},\dots,x_{n-1})$
\end_inset

,
 for every 
\begin_inset Formula $(x_{1},\dots,x_{n})\in S\setminus\{\emptyset\}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc3[M23]
\end_layout

\end_inset

If it is possible to tile the upper right quadrant of the plane when given an 
\emph on
infinite
\emph default
 set of tetrad types,
 is it always possible to tile the whole plane?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

No.
 For example,
 our tiles might be of the form
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{center}
\end_layout

\begin_layout Plain Layout


\backslash
begin{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
draw (0,0) -- (0,2) -- (2,2) -- (2,0) -- (0,0) -- (2,2)
\end_layout

\begin_layout Plain Layout

      (0,2) -- (2,0)
\end_layout

\begin_layout Plain Layout

      (0.5,1) node{$n$} (1,0.5) node{$n$}
\end_layout

\begin_layout Plain Layout

      (1.5,1) node{$n+1$} (1,1.5) node{$n+1$};
\end_layout

\begin_layout Plain Layout


\backslash
end{tikzpicture}
\end_layout

\begin_layout Plain Layout


\backslash
end{center}
\end_layout

\end_inset

for 
\begin_inset Formula $n\in\mathbb{N}$
\end_inset

.
 Then in the 
\begin_inset Formula $(x,y)$
\end_inset

 square we might place the tile with 
\begin_inset Formula $n=\max\{x,y\}$
\end_inset

 and this would tile the upper right quadrant,
 but there's obviously no way to tile the whole plane.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc6[M23]
\end_layout

\end_inset

(Otto Schreier.) In a famous paper,
 B.
 L.
 van der Waerden proved the following theorem:
\end_layout

\begin_layout Quote

\shape slanted
If 
\begin_inset Formula $k$
\end_inset

 and 
\begin_inset Formula $m$
\end_inset

 are positive integers,
 and if we have 
\begin_inset Formula $k$
\end_inset

 sets 
\begin_inset Formula $S_{1},\dots,S_{k}$
\end_inset

 of positive integers with every positive integer included in at least one of these sets,
 then at least of the sets 
\begin_inset Formula $S_{j}$
\end_inset

 contains an arithmetic progression of length 
\begin_inset Formula $m$
\end_inset

.
\end_layout

\begin_layout Standard
(The latter statement means there exist integers 
\begin_inset Formula $a$
\end_inset

 and 
\begin_inset Formula $\delta>0$
\end_inset

 such that 
\begin_inset Formula $a+\delta$
\end_inset

,
 
\begin_inset Formula $a+2\delta$
\end_inset

,
 ...,
 
\begin_inset Formula $a+m\delta$
\end_inset

 are all in 
\begin_inset Formula $S_{j}$
\end_inset

.) If possible,
 use this result and the infinity lemma to prove the following stronger statement:
\end_layout

\begin_layout Quote

\shape slanted
If 
\begin_inset Formula $k$
\end_inset

 and 
\begin_inset Formula $m$
\end_inset

 are positive integers,
 there is a number 
\begin_inset Formula $N$
\end_inset

 such that if we have 
\begin_inset Formula $k$
\end_inset

 sets 
\begin_inset Formula $S_{1},\dots,S_{k}$
\end_inset

 of integers with every integer between 1 and 
\begin_inset Formula $N$
\end_inset

 included in at least one of these sets,
 then at least one of the sets 
\begin_inset Formula $S_{j}$
\end_inset

 contains an arithmetic progression of length 
\begin_inset Formula $m$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

It is enough to prove it when the set that contains every integer between 1 and 
\begin_inset Formula $N$
\end_inset

 is 
\begin_inset Formula $S_{1}$
\end_inset

.
 We define a tree whose vertices are the tuples 
\begin_inset Formula $(S_{1},\dots,S_{k})$
\end_inset

 of finite sets of integers such that,
 if 
\begin_inset Formula $n=\max\bigcup_{i=1}^{k}S_{i}$
\end_inset

,
 every positive integer up to 
\begin_inset Formula $n$
\end_inset

 is in one of the sets,
 and such that no set contains an arithmetic progression of length 
\begin_inset Formula $m$
\end_inset

.
 The edges go from one such tuple to 
\begin_inset Formula $(S_{1}\setminus\{n\},\dots,S_{k}\setminus\{n\})$
\end_inset

,
 so the root is 
\begin_inset Formula $(\emptyset,\dots,\emptyset)$
\end_inset

 and 
\begin_inset Formula $n$
\end_inset

 is the height of the node in the tree.
\end_layout

\begin_layout Standard
Since each vertex contains a finite number of children (
\begin_inset Formula $2^{k}-1$
\end_inset

,
 corresponding to the ways of adding the next number to one or more of the sets),
 it follows that if this tree were infinite,
 there would be an infinite path.
 By van der Waerden theorem,
 the component-wise union of this path would give us a tuple 
\begin_inset Formula $(S_{1},\dots,S_{k})$
\end_inset

 such that some 
\begin_inset Formula $S_{j}$
\end_inset

 contains an arithmetic progression of length 
\begin_inset Formula $m$
\end_inset

,
 so by construction one of the nodes in the path would follow this condition.
\begin_inset Formula $\#$
\end_inset


\end_layout

\begin_layout Standard
Thus the tree is finite and we just need to take 
\begin_inset Formula $N$
\end_inset

 as one plus the depth of the tree.
\end_layout

\end_body
\end_document