% В тираж!
\documentstyle{amsppt}
\loadbold
\NoBlackBoxes
\TagsAsMath
\TagsOnRight
\magnification 1200
\topmatter
\rightheadtext{Lines on Grid Paper and Superwords}
\address
\endaddress
\email
kanel\@mccme.ru \,\, M.L\@gerver.mccme.ru
\endemail
\endtopmatter
\define\ar{\rightleftarrows}
\define\a{\alpha}
\redefine\b{\beta}
\redefine\l{\lambda}
\define\f{\varphi}
\define\p{\Pi}
\document
\head { Preparatory Problems. Keys and Solutions } \endhead
0.1. Superwords~$W=\dots v v h v v \dots$ from letters $v$ with
the only letter $h$ certainly does not belong to
class $S$. Another example of such superword~$W$:
$\dots v v v h h h \dots$ (first letters~$v$ only, then
letters $h$ only).
0.2.1. For lines $L$ with finite slope $k_L$
superwords $W_L$ are periodic if and only if $k_L$ is rational.
For $k_L=\infty$, i.e., for vertical line $L$ superword $W_L$
is periodic too since it consists of letters $h$ only.
0.2.2. If line $L$ has slope $k_L<1$
then letters $v$ occur more often then $h$ in superword~$W_L$.
0.2.3. Substitute $h \ar v$ in any superword $W_L$ from
$S$. The resulting superword $W^{\prime}$ remains in class $S$
since $W^{\prime} = W_{L^{\prime}}$ for line $L^{\prime}$
with slope $k_{L^{\prime}} = 1/k_L$.
0.3. Superword
$W = \{\dots h\, v\, v\, v\, h\, v\, v\, h \dots\} \in S$ because
all the squares of polygon $M_w$ corresponding to word
$w=\{h\, v\, v\, v\, h\, v\, v\, h\}$ can be crossed by a line
(for example, with slope $k_L=3/7$).
0.3.1. Between any two {\it consecutive\/} letters $h$ in $W$
can be {\it either two or three\/} letters $v$. Let us prove it.
If a superword $W_L \in S$ contains subword $hv^kh$
($k$ letters $v$ between two consecutive $h$) then slope
$k_L$ is, clearly, confined between $1/(k+1)$ and $1/(k-1)$.
The word $ h v v v h v v h $ contains subwords $hv^kh$ for $k=2$ and
$k=3$. Therefore $k_L \in [1/3, 1/2]$.
Moreover, $k_L \ne 1/3$ and $k_L \ne 1/2]$ (why?).
Hence $k_L \in (1/3, 1/2)$; but this implies $2\le k \le 3$
for any subword $hv^kh \in W$, QED.
0.3.2. Let us list all different subwords of length 2, 3 and 4 in $W$:
\centerline
{3 words of length 2: $ hv, vv, vh$; \quad
4 words of length 3: $ vvv, hvv, vhv, vvh$; }
\centerline
{5 words of length 4: $hvvv, vhvv, vvhv, vvvh, hvvh$. }
0.3.3. Superwords~$W_L$ and $W_{L^*}$ contain subword
$ h v v v h v v h $, for example, for parallel lines
$L$ and $L^*$ with slope
$k_L=3/7$; slopes $k_L=3/8$ and $k_L=2/5$ will work too (check it).
Same applies to $k_L$ close enough to the above values.
0.3.4. In view of 0.3.1, superword $W$ in 0.3 is
$\{\dots v\, v\, h\, v\, v\, v\, h\, v\, v\, h\, v\, v \dots\}$.
Therefore, $W$ contains the following 6 subwords of length 5:
$hvvvh, vhvvv, vvhvv, vvvhv, vhvvh, hvvhv$
and 7 subwords of length 6:
$vhvvvh, hvvvhv, vvhvvv, vvvhvv, vvhvvh, vhvvhv, hvvhvv$.
Since between any two consecutive letters $h$ in $W$
are {\it al least two and at most three\/} letters $v$,
any subword $W$ of length 5 or 6 contains either one or two letters
$h$. Simple check proves that above listed are
{\it all\/} subwords
of lengths 5 and 6 in $W$.
Therefore, for any two lines $L$ and ${L^*}$ crossing
all squares of polygon $M_w$ corresponding to word
$w=\{h\, v\, v\, v\, h\, v\, v\, h\}$,
sets of all five-letter and six-letter subwords of
$W_L$ and $W_{L^*}$ necessarily coincide.
On the contrary, sets of all seven-letter subwords in
$W_L$ and $W_{L^*}$ need not coincide for all $L$ and $L^*$.
For example, let $L$ and ${L^*}$ have slopes $k_L=3/7$ and
$k_{L^*}=3/8$, respectively. In this case
$W_L$ are $W_{L^*}$ are periodic superwords
{$\{h\, v\, v\, v\, h\, v\, v\, h\, v\, v\}$ and $\{h\, v\, v\, v\, h\,
v\, v\, v\, h\, v\, v\}$,} so $W_L$ contains subword $\{h\, v\, v\,
h\, v\, v\, h\}$, which $W_{L^*}$ misses, and $W_{L^*}$ contains subword
$\{v\, v\, v\, h\, v\, v\, v\}$, which $W_L$ misses.
0.4.1. It can happen that all subwords of a superword $W$ are
permitted, but $W \not\in S$.
An example of such a word is already given in 0.1: it is superword
$W=\dots v v h v v \dots$ of letters $v$ with the only $h$.
0.4.2. Superwords $W_L$ and $W_{L^*}$ may coincide even if lines $L$ and
$L^*$ do not: this will be the case if $L^*$ is symmetric to $L$
(taking orientation into account) with respect to a vertical,
a horizontal or a knot of the grid; it will also be
the case if the lines are parallel and $L^*$ is $L$ shifted by 1 (or
any integer) along vertical or horizontal direction.
If we want that different words correspond {\it generically\/} (see 0.4.3)
to different lines $L$ and
$L^*$, we can fix a square $K_0$ and consider only lines with
positive slopes that pass through $K_0$ and cross the same side of it.
0.4.3. Let lines $L$ and $L^*$ have the same slope $k_L$
and let none of them pass through grid knots.
If, moreover, $k_L$ is rational, then (as it is readily seen)
superwords $W_L$ and $W_{L^*}$ coincide.
If instead $k_L$ is irrational, then the set of all subwords
in $W_L$ and $W_{L^*}$ coincide, while $W_L$ and $W_{L^*}$
need not coincide (and they do not if $L$ and $L^*$
pass through the same side of square $K_0$, see 0.4.2).
At this stage -- solving preparatory problems -- we will only
formulate the above statement; try to prove it on your own.
Also try to prove another fact -- {\it quasiperiodicity} of $W_L$:
if slope $k_L$ is irrational then $W_L$ contains arbitrary long
coinciding subwords.
0.5.1. Erase one $v$ in front of each $h$ in $W \in S$ from 0.3.
The resulting superword $\{\dots h v v h v h \dots\}$
remains in class $S$. In general case this fact is proved in
0.5.2. Intuition for 0.5.2: if lines $L_1$
and $L_2$ have slopes $k_{L_1}=3/4$ and $k_{L_2}=3/5$, then $W_{L_1}$ and
$W_{L_2}$ are periodic superwords with periods $\{h v v h v h
v\}$ and $\{h v v h v v h v\}$ (compare to 0.3.4).
0.5.2. Let line $L$ with slope $k_L<1$ cross some horizontal $g$ at
point $P$. Erase one
$v$ in front of each $h$ in superword $W_L$. the resulting
superword $W^*$ remains in class $S$ since $W^* = W_{L^*}$
for line $L^*$ that passes through $P$ with slope $k_{L^*}$
such that $1/{k_{L^*}}=1/{k_L}-1$.
0.6. Let line $L$ with slope $k_L<1$ cross some horizontal
$g$ at point $P$.
Insert one $v$ in front of each $h$ in superword $W_L$. Then the
resulting superword $W^*$ remains in class $S$ since $W^* =
W_{L^*}$ for line $L^*$ that passes through $P$ with slope $k_{L^*}$
such that $1/{k_{L^*}}=1/{k_L}+1$.
0.7. If line $L$ has slope $k_L$ then
$W_L \in E$ if and only if $k_L = 1$;
$W_L \in S^h_{\infty}$ if and only if $k_L = 0$;
$W_L \in S^v_{\infty}$ if and only if $k_L = \infty$;
$W_L \in S^h_n$ if and only if $k_L \in (1/(n+1),1/n]$;
in this case $k_L = 1/n$ if and only if there are $n$ letters $v$ between
any two consecutive letters $h$.
$W_L \in S^v_n$ if and only if $k_L \in [n,n+1)$;
in this case $k_L = n$ id and only if there are $n$ letters $h$
between any two consecutive letters $v$.
0.7.1. Geometric interpretation of 0.7 in terms of strip polygons is
as follows: lengths $\l_s$ of strip polygons
$M_w$ for a permitted word $w$ that is a subword of a superword
$W \in S^h$ can take at most two values:
all lengths $\l_s = n+1$ if there are $n$ letters $v$ between any two
consecutive letters $h$;
lengths $\l_s$ are equal either to $n+1$ or to $n+2$ if $W_L \in S^h_n$
and $k_L \ne 1/n$.
\noindent
if strip lengths $\l_s$ of
$M_w$ take more than two values, then
word~$w$ is {\it necessarily} forbidden.
if strip lengths $M_w$ take only two values,
word $w$ may {\it still } be forbidden (see 0.7.2).
For superwords $W\in~S^v$ one must substitute $v \ar h$ before counting
the number of $\l_s$ values.
0.7.2. Here is an example of a periodic forbidden word $w$ for which
lengths $\l_s$ of strips in $M_w$ take two values 2 and 3. It has the
following ten-letter period: {$\{h v h v h v v h v v\}$.}
Check that corresponding polygon $M_w$ can not be crossed by a
single line.
0.8.1. Let the slope $k_L$ of line $L$ be equal to a
{\it finite\/} continued fraction, for example, one of the following:
\eightpoint
$$
\frac{11}{25}=
\dsize\frac{1}{2+\dsize\frac{1}{3+\dsize\frac{1}{1+\frac{1}{2}}}},
\quad
\frac{7}{24}=
\dsize\frac{1}{3+\dsize\frac{1}{2+\dsize\frac{1}{3}}},
\quad
\frac{4}{19}=
\dsize\frac{1}{4+\dsize\frac{1}{1+\dsize\frac{1}{3}}},
\quad
\frac{5}{8}=
\dsize\frac{1}{1+\dsize\frac{1}{1+\dsize\frac{1}{1+\frac{1}{2}}}}.
$$
\tenpoint
For each of these fractions let us find the chain $a_1,\, a_2,\, \dots,
a_n$ for superword $W=W_L$.
If $k_L=11/25 \in (1/3,1/2]$ then $W=W_L\in S^h_2$ (see 0.7).
Hence $a_1=2$. Erase $a_1$ letters $v$ in front of each $h$ and
denote the resulting superword by $W_1$. By
0.7 and 0.5.2 we have:
$W_1=W_{L_1}\in S^v_3$ since $25/11 - 2 = 3/11 \in (1/4,1/3]$.
Hence $a_2=3$. Erase $a_2$ letters $h$ in front of each $v$.
We get $W_2=W_{L_2}\in S^h_1$ since $11/3 - 3 = 2/3 \in
(1/2,1]$.
Hence $a_3=1$. Erase $a_3$ letters $v$ in front of each $h$ and
denote the resulting superword by $W_3$. Now $W_3\in S^v_2$
because $3/2 - 1 = 1/2$.
Hence $a_4=2$. Erase $a_4$ letters $h$ in front of each $v$.
We get $W_4\in S^h_{\infty}$. Therefore,
if $k_L=11/25$ then $a_1=2,\, a_2=3,\, a_3=1,\, a_4=2$.
{\it Corollary}. If $k_L=11/25$ then $W_j$ are the superwords with the
following periods:
$W_4=\{\dots v \dots\}$;
$W_3=\{\dots hhv \dots\}$;
$W_2=\{\dots vvh vh \dots\}$;
$W_1=\{\dots vh^4 vh^4 vh^3 \dots\}$;
$W= \{\dots hv^2 hv^2 hv^2 hv^3\,\, hv^2 hv^2 hv^2 hv^3\,\, hv^2 hv^2
hv^3 \dots\}$.
Similarly, for $k_L=7/24$ we have $a_1=3,\, a_2=2,\, a_3=3$;
if $k_L=4/19$ then $a_1=4,\, a_2=1,\, a_3=3$,
and if $k_L=5/8$ then $a_1=a_2=a_3=1, a_4=2$.
0.8.2. If slope $k_L$ of line $L$ is rational:
\eightpoint
$$
k_L =
\dsize\frac{1}{a_1+\dsize\frac{1}{a_2+\dsize\frac{1}{a_3+\dots+
\dsize\frac{1}{a_n}}}},
$$
\tenpoint
then reorganizations of the superword $W=W_L$, corresponding to line $L$,
stop after finitely many steps:
$W \to W_1 \to W_2 \to \dots \to W_n$
and result in series $a_1,\, a_2,\, \dots, a_n$.
\smallpagebreak
1.1. The simplest examples of carefully mixed words are
\centerline
{$\{\dots a a a \dots\}$ \, and \, $\{\dots b b b \dots\}$.}
A second simplest example: superword
$W=W_L\in S$ for line $L$ with slope $k_L$
equal to either $n$ or $1/n$. For instance, let $k_L = 1/n$.
By 0.7 in $W=W_L$ in this (and only this) case there are $n$ letters
$v$ between any two consecutive $h$:
\centerline
{$W = \{\dots h v h v h v \dots \}$ for $n=1$,
$W = \{\dots h v v h v v h v v \dots \}$ for $n=2$, etc.}
That such $W$ are carefully mixed is obvious:
$W = \{\dots h v^n h v^n h v^n \dots \}$
any subword of length $r \le n$ contains either $r$ letters $v$,
or one letter $h$ and $r-1$ letters $v$;
any subword of length $(n+1)k+r$, where $0 \le r \le n$,
contains either $k$ letters $h$ and $nk+r$ letters $v$,
or $k+1$ letters $h$ and $nk+r-1$ letters $v$.
1.2.1. Any permitted word $w$ is, obviously, a subword of infinitely many
different superwords $W_L$ from
$S$: if polygon $M_w$ can be crossed by a line $L$ that does not pass
through knots then it can as well be crossed by any line $L^*$ close
enough to $L$.
1.2.2. In particular, line $L^*$ from 1.2.1 can be chosen with rational
slope $k_L$.
1.2.3. It follows from the definition of a carefully mixed word that a
superword $W$ is carefully mixed if and only if each its subword
is carefully mixed.
1.3.1. Answer: {\it no}.
Replace letters $a$ and $b$ with $h$ and $v$.
Here is a counterexample:
$w=hvvhvvhvhv$
is permitted while $w^*=vvhh$ is forbidden.
To elaborate a little: $w=hvvhvvhvhv$ is permitted
since $w^{\prime}=hvvhvvhvhvv$ is permitted
(and $w^{\prime}=hvvhvvhvhvv$ is permitted since
${w^{\prime}}^*=vvhv$ is permitted,
see the theorem below).
The following theorem holds:
{\it renaming maps
1) superwords~$W \in S$ to superwords~$W^* \in S$,
2) forbidden words~$W$ to forbidden words~$W^*$,
3) superwords~$W \not\in S$ to superwords~$W^*
\not\in S$}.
We sketch the proof.
Let $M_W$ be the strip polygon for word~$W$. Boundaries of
$M_W$ are broken lines $\underline L$ and $\overline L$,
with units along verticals and horizontals of the grid. For subwords
of $W$ of types $hv^n$ and $hv^{n+1}$ adjacent units of these broken
lines are legs of right triangles of two kinds. Hypotenuses of these
triangles form new broken lines $\underline L^{\prime}$ and
$\overline L^{\prime}$ inside $M_W$. Units of both these new
broken lines lie on a {\it new\/} grid generated by lines with slopes
$1/n$ and $1/(n+1)$ (the knots of the new grid are the same as of
the old one), so each unit corresponds either to word $hv^n$ or to
word $hv^{n+1}$.
Introduce coordinates $x, y$ on the grid and consider transformation~$F$
that maps point $\{x,y\}$ into $\{x-ny, -x+(n+1)y\}$.
This transformation maps vectors
$\{n+1,1\}$ and $\{n,1\}$ to vectors $\{1,0\}$ and $\{0,1\}$,
broken lines $\underline L^{\prime}$ and
$\overline L^{\prime}$ to broken lines
$\underline L^{*}$ and $\overline L^{*}$
with units along horizontals and verticals of the grid.
Therefore transformation~$F$ corresponds to renaming
(replacing words $hv^{n+1}$ with letters $v$ and words
$hv^n$ with letters $h$): if we denote by $M^*$ the polygon
bounded by broken lines $\underline L^{*}$ and $\overline
L^{*}$ then it will turn out to be the strip polygon for word~$W^*$.
In what follows we need the following properties of linear
transformations $F$:
$F$ maps lines to lines and preserves ratios of segment
lengths.
1.3.2. Solutions of problem 1.3.2 {\it are still accepted}.
We will need the following theorem about superwords:
{\it Renaming maps superwords
$W\in S_1$ to superwords $W^*\in S_1$ and superwords
$W \not\in S_1$ to superwords $W^*\not\in S_1$.}
Let us prove the first part of the theorem.
By hypothesis superword $W$ can be split into subwords of two types:
$ab^n$~and $ab^{n+1}$ (when you solve problem 1.3.2 you may
conveniently relate to them as {\it short and long segments}).
Now perform the following {\it renaming}: we replace each subword
$ab^{n+1}$ by $b$ and each subword $ab^{n}$ by $a$.
Denote by $W^*$ the resulting image of $W$.
Introduce the following notation for each word $w$:
$a(w)$ is the number of letters~$a$ in $w$, $b(w)$ is the number of
letters~$b$ in $w$; $|w|$ is the length of $w$. \remark{\quad
Remark} Below we draw on the following statement (prove it):
In any word (or superword) $W^*\not\in S_1$ there exist two subwords
$U^*$ and $V^*$ of the same length for which
$b(U^*)-b(V^*) = 2$.
\endremark
Consider a superword $W\in S_1$. We want to prove that superword
$W^*\in S_1$. Assume the converse: suppose there exist two
subwords $U^*$ and $V^*$ in $W^*$ such that $|U^*|=|V^*|$ and
$b(U^*)-b(V^*) = 2$. The last two equalities imply that the
following holds for words $U$ and $V$ that are mapped to $U^*$ and
$V^*$ by renaming transformation:
\centerline
{$|U|-|V|= b(U)-b(V)=2$.}
Of subwords $U$ and $V$ build two subwords
$U^{\prime}$ and $V^{\prime}$ of superword~$W$.
Words $U$ and $V$ consist of segments $ab^n$~and $ab^{n+1}$;
word $U^{\prime}$ is $U$ with erased first~$a$ and word~$V^{\prime}$
is $V$ with another~$a$ at the tail. Hence
\centerline
{$|U^{\prime}|=|V^{\prime}|$, \quad $b(U^{\prime})-b(V^{\prime})=2$.}
\noindent
That such $U^{\prime}$ and $V^{\prime}$ are subwords of
$W$ contradicts the hypothesis that $W\in S_1$. Therefore
$W^*\in S_1$ is proved by contradiction.
1.4.1. Let us prove that each permitted word $W$ is carefully mixed.
Let $U$ and $V$ be any two its subwords of the same length such that
$U$ has $n$ letters $h$ and $m$ letters $v$ while $V$ has $n+d$
letters $h$ and $m-d$ letters $v$ where $d\ge 0$. Assume
that the strip polygon of $W$ can be crossed by a line $L$ with
slope $k$. Since this line crosses the polygon of word $U$, we have
$\frac{m-1}{n+1} < k$. On the other hand, crossing the polygon of $V$
gives $k < \frac{m-d+1}{n+d-1}$. Therefore $\frac{m-d+1}{n+d-1} >
\frac{m-1}{n+1}$, or $(n+m)(2-d) > 0$. Hence $d<2$, i.e., $W$ is
carefully mixed.
1.4.2. Any superword $W \in S$ is carefully mixed since,
by~1.4.1, every its subword is carefully mixed and by~1.2.3 a
superword is carefully mixed if and only if so are all of its
subwords.
1.4.3. We have already come across an example of carefully mixed
superword $W \not\in S$ twice - see solutions of 0.1 and 0.4.1: it is
superword~$W=\dots v v h v v \dots$ of letters $v$ with the only letter
$h$.
1.5. lets prove that for any relatively prime $m$ and $n$ there
exists a periodic carefully mixed superword of letters $a$ and $b$ with
$m$ letters $a$ and $n$ letters $b$ in its period.
Consider $W_L \in S$, where $L$ is a line with slope~$m/n$.
To get $W$ out of $W_L$ it suffices to substitute $h \to a$, $v \to b$
in $W_L$.
If $m$ and $n$ are not relatively prime then there exists no
periodic carefully mixed superword $W$ such that its
{\it shortest\/} period has $m$ letters $a$ and $n$ letters $b$.
Take, for example, $m=2$, $n=4$. Then for
\centerline
{$W = \{a \,b \,b \,a \,b \,b\} = \{b \,a \,b \,b \,a \,b\}
= \{b \,b \,a \,b \,b \,a\}$}
\noindent
the period of length six is not the shortest and none of the other
superwords with periods of two letters $a$ and four letters $b$
is carefully mixed since they all have subwords $aab$ and
$bbb$.
If we relax the requirement that the period be the shortest then
the statement is true for all $m$ and $n$, not necessarily relatively
prime.
1.6.1. Solutions of 1.6.1 {\it are still accepted}.
1.6.2. Solutions of 1.6.2 {\it are still accepted}.
1.7. We start describing superwords $W$ that are in $S_1$
but not in $S$. It will bring us for problems 3.1.1-3.1.3 of the main
list; solving them will help you continue the description.
According to 1.2.3, a superword $W\in S_1$ if and only if every its
subword $w$ is carefully mixed. By 1.6.2 any carefully mixed word $w$
is permitted. Hence for each $w\in W$ strip polygon $M_w$ can be
crossed by a line $L(w)$ that does not pass through knots.
Consider an embedded sequence $w_1 \subset w_2 \subset \dots$ of
subwords $w_n\in W$, that converges to~$W$ (meaning that each letter of
$W$ belongs to all $w_n$ for $n$ large enough). Corresponding to it is
an embedded sequence of strip polygons $M_n$ with common square $K_0$.
Each of these polygons can be crossed by a line $L_n$ passing through $K_0$.
Let $y=k_nx+b_n$ be the equation of~$L_n$.
Sequences $k_n$ and $b_n$ are bounded (check it). Hence we can choose a
subsequence of pairs $k_{n_j}, b_{n_j}$ converging to $k, b$.
Line $L$ given by equation $y=kx+b$ has a common point with each
of the strip polygons $M_n$. It must pass through at least one knot
of the grid (why?).
To be continued in problems 3.1.1-3.1.3.
1.8. Generalize the definition of carefully mixed superwords of
alphabets of more than two letters: $a, b, c, \dots$.
Superword $W$ is carefully mixed if the number of letters $a$ in any
two of its subwords $U$ and $V$ of the same length differs
at most by one1; we require the same for letters $b$, letters $c$ and
so on.
Here is an example of a {\it periodic\/} carefully mixed superword of
letters $a,b,c$ containing the superword $aa$: $W =
\{\dots\{a\, a\, b\, a\, c\, a\, b\, a\, c\,\}\dots\}$. To see
that $W$ is carefully mixed we construct three auxiliary superwords
of letters $v,h$.
The first is $W$ where $a$ is replaced by $v$, $b$ and $c$
by $h$: {$W_1 = \{\dots\{v\, v\, h\, v\, h\, v\, h\, v\,
h\,\}\dots\}$.}
The second is $W$ where $a$ and $c$ are replaced by $v$, $b$
by $h$: {$W_2 = \{\dots\{v\, v\, h\, v\, v\, v\, h\, v\,
v\,\}\dots\}$.}
The third is $W$ where $a$ and $b$ are replaced by $v$, $c$
by $h$: {$W_3 = \{\dots\{v\, v\, v\, v\, h\, v\, v\, v\,
h\,\}\dots\}$.}
All three auxiliary words belong to $S$:
\centerline
{$W_1 = W_{L_1}$, \quad $W_2 = W_{L_2}$, \quad $W_3 = W_{L_3}$}
\noindent
for lines $L_1, L_2, L_3$ with slopes
$k_{L_1}=4/5$, $k_{L_2} = k_{L_3}= 2/7$.
Hence all of them are carefully mixed; in particular, the number of
letters $v$ in any two subwords $U$ and $V$ of $W_1$ of the same
length differs at most by one. But then the number of letters $a$ in
any two subwords $U$ and $V$ of $W$ of same length differs at
most by one. Similar argument (applied to subwords of $W_2$ and
$W_3$, respectively) shows that so do the numbers of letters $b$ and
letters $c$ in any two subwords of $W$ which completes that
proof.
\smallpagebreak
2.1. By $T_W(n)$ denote the number of different subwords of
length~$n$ in superword $W$.
Maximum possible value of $T_W(n)$ for a two-letter alphabet is
obviously equal to~$2^n$
($3^n$ for a three-letter alphabet, $m^n$ for an $m$-letter
alphabet).
2.2. Suppose $T_W(k)=T_W(k+1)=T$ for some~$k$
(that is, the number of different subwords of length $k$ in
superword $W$ is equal to the number of different subwords of
length $k+1$ denoted by $T$).
Let us prove that in this case superword $W$ is periodic with period
$T$.
For each $d$ every subword of length $d$ in superword $W$ can be
extended to the right to a subword of length $d+1$ at most in
two ways (with either $a$ or $b$). Equality
$T_W(k)=T_W(k+1)$ means that for $d=k$ only one way exists:
if a subword of length $k$ could be continued in two different ways we
would end up with more than $T_W(k)$ words of length $k+1$.
Likewise any two coinciding subwords of $W$ of length $k$ have
the same letter to the left of them.
Write down $T+k$ consecutive letters $w_1, \dots, w_{T+k}$
of superword $W$ and (respectively) $T+1$ subwords $W_0, \dots, W_T$
of length $k$ composed of these letters.
\centerline
{$W_0=\{w_1, \dots, w_k\}$, \dots,
$W_{T}=\{w_{T+1}, \dots, w_{T+k}\}$.}
Since the number of different subwords of length $k$ in superword $W$
is $T$, we have $W_i = W_j$ for some $i$ and $j$:
\centerline
{$W_{i}=\{w_{i+1}, \dots, w_{i+k}\} =
W_{j}=\{w_{j+1}, \dots, w_{j+k}\}, \,\, 0 \le i < j \le T$,}
\noindent
or, equivalently,
\centerline
{$W_{i}=\{w_{i+1}, \dots, w_{i+k}\} =
W_{i+P}=\{w_{i+P+1}, \dots, w_{i+P+k}\}, \,\, 1 \le P=j-i \le T$.}
Since any subword of length $k$ of superword $W$ can be
uniquely expanded to the right and to the left, the above implies that
\centerline
{$W_{s}=\{w_{s+1}, \dots, w_{s+k}\} =
W_{s+P}=\{w_{s+P+1}, \dots, w_{s+P+k}\}$, \,\, for any integer $s$,}
\noindent
i.e. superword $W$ is periodic and the length of period $P \le T$.
Since the number of $k$-letter subwords of such a superword is $P$ and
by hypothesis it is $T$, we have $P=T$.
{\it Remark.} Therefore, $i=0, j=T$ and
\centerline
{$W_{0}=\{w_{1}, \dots, w_{k}\} =
W_{T}=\{w_{T+1}, \dots, w_{T+k}\}$.}
2.3. Suppose $T_W(k) k+1$ can
hold. Assume the converse and take one $k$ for which it holds.
Let $w$ be a subword of superword $W$ having $k+2$ subwords of $W$
of length $k$.
By 1.2.2 there exists a line $L^*$ with {\it rational\/} slope
that crosses strip polygon $M_w$.
Word $w$ is a subword of superword $W^*=W_{L^*}$, i.e.,
$T_{W^*}(k) \ge k+2 > k+1$ against 2.4.1. This contradiction
implies that our assumption was wrong and hence $W=W_L$ satisfies
$T_W(k)=k+1$ for all $k$, i.e.,
$W\in S_2$.
2.4.3. An example of a superword $W\in S_2$ not belonging
$S$ already showed up in solutions for 0.1:
$\dots v v v h h h \dots$ (first letters $v$ only, then letters
$h$ only).
2.4.4. All superwords $W$ such that $W \in S_1$ and $W \not\in S$,
belong to $S_2$.
To be continued in problems 3.3, 3.4.1-3.4.3 of the main list.
\end