% � �ࠦ!
\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$ for a certain $k$. Let us prove that then 
$W$~is periodic. 

If $W = \{\dots a a a \dots\}$ or $W = \{\dots b b b \dots\}$ 
(if $T_W(k)=1\le k$ for all~$k$) then the statement holds: 
$W$~is periodic. 

Let us now suppose that $W$ contains both letters $a$ and letters $b$.  
Then 

\centerline
{$2 \le T_W(1) \le T_W(2) \le \dots \le T_W(k) \le k$, }

Since $k$ numbers $T_W(i)$ take $k-1$ values, there exits $i$ such 
that $T_W(i+1) = T_W(i)$. The periodicity of $W$ follows now from 2.2.

2.4. Let us prove that for all $W \in S$ the following 
inequality holds: 

\centerline
{$T_W(k) \le k+1$ for all $k$.} 

2.4.1. We start with description of $T_W(k)$ for $W=W_L$ in case of 
rational slope  $k_L = m/n$ (for mutually prime $m$ and $n$). 

In this case, as it can be easily seen, $T_W(k)=k+1$ for $k < P=m+n$ 
and $T_W(k)=P$ for $k \ge P$, so for rational $k_L$ inequality $T_W(k) 
\le k+1$ is proved for all $k$. 

2.4.2. Suppose now that $k_L$ is irrational. Let us prove that 
$W=W_L$ satisfies $T_W(k)=k+1$ for all $k$ and thus  
$W\in S_2$. 

By 2.3 we have $T_W(k) \ge k+1$ for all $k$. 
What is left is to prove that for no $k$ inequality $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 


