%&russiantex
\magnification 1100
\hmargins 15truemm, 15truemm
\vmargins 25truemm, 20truemm

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% English / Russian
\long\def\pargobble#1\par{}
\let\rus\empty\let\eng\empty
\def\russian{\let\eng\pargobble\let\rus\empty}
\def\english{\let\rus\pargobble\let\eng\empty}
\def\ruseng#1#2{\relax\ifx\rus\empty#1\else#2\fi}
\def\checkrus#1777#2\endcheck{\def\tempa{#2}\ifx\tempa\empty\else\russian\fi}
\def\checkeng#1111#2\endcheck{\def\tempa{#2}\ifx\tempa\empty\else\english\fi}
\expandafter \checkrus \jobname 777\endcheck
\expandafter \checkeng \jobname 111\endcheck
\newcount\engrusc
\russian
%\english
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Fonts
\font \tenbff = labx3583 at 10pt
\font \titlefont = lasx500 at 21pt
\font \wasy = wasy10 at 48pt
\font \pgnumfont = lasx500 at 21pt
\newfam \bfitfam
\font \bfitfont = labi1000 \textfont\bfitfam \bfitfont
\def \bfit{\fam\bfitfam\bfitfont}

\def\hexagon{{\wasy \char 57}}
\hyphenchar\tensl 127


\headline {\hfil \ooalign{\cr\hfil\hexagon\hfil\cr\hfil\raise 5pt\hbox{\pgnumfont\the\count0}\hfil}}
\nopagenumbers

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Symbols and macros
\newskip \softfillskip \softfillskip 0pt plus 1000pt 
\ifx \blacklozenge\undefined 
  \font\larm = larm1000
  \font\tenbf = labx1000
  \font\tensl = lasl1000
  \font\tenit = lati1000
  \larm
  \tolerance 999
  \font \msamten = msam10
  \textfont9 \msamten
  \mathchardef\blacklozenge = "907   
  \def\centering{\leftskip\softfillskip \rightskip\leftskip \parindent 0pt \parfillskip 0pt\relax}
  \def\rgbcolor#1{}
  \def\small{}
  \def\boldmath{}
  \def\normalmath{}
  \let\hm\relax
  \def\includegraphics#1{\special{psfile="#1" }}
  \def\grefincrement#1{\global\advance#1 by 1 }
  \fi

\let\lt \bf
\catcode`�=13 \def �{<<}
\catcode`�=13 \def �{>>}
\catcode`�=13 \def �#1�{{\bf#1\/}}
\catcode`�=13 \let�'
\catcode`�=13 \def �{\unskip~---}
\def\1~{\penalty 70   \ }
\def\2~{\penalty 200  \ }
\def\3~{\penalty 9999 \ }
\let\phi\varphi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Sections
\def\temp{\rgbcolor{1 0 0}}
\long\def\myempty#1{}
\def\prenum{\indent\llap{\hbox to \parindent{$\blacklozenge$\hfil}}}
\def\taskstyle{\tenbff\sl}
\def\taskx#1.{\par\smallbreak{\bf{\prenum#1.\enspace}}\begingroup
    \taskstyle\def\par{\endgraf\endgroup\smallbreak}\interlinepenalty9999 \ignorespaces}
\def\rustask{\rus\taskx}
\def\engtask{\eng\taskx}
\def\task{\global\advance\engrusc 1 \ifodd\engrusc\expandafter\rustask\else\expandafter\engtask\fi}

\def\sect#1.#2\par{\par\goodbreak\bigskip {\centering\bf \sectionname\ #1. \ignorespaces#2\par}\nobreak\medskip}
\def\subsect#1{\par{\bf#1\par}}
\def\problem#1{\par{\noindent\titlefont#1}\par\bigskip}

\newcount\figurec
\def\figure#1{\par{\centering\grefincrement\figurec \figurename\ \the\figurec.~#1\par}}

\def\quote{\begingroup \small }
\def\endquote{\par\endgroup}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\logo{\raise -30pt \hbox{{\includegraphics{../figs/tiling.0}}}}

\parskip=\smallskipamount

\rus
\def\figurename{�������}
\def\sectionname{����}
\binoppenalty = 10000
\relpenalty = 10000

\eng
\def\figurename{Figure}
\def\sectionname{Section}


\problem{\logo \hfil \vbox{\halign{\hfil#\hfil\vbox to 17pt{} 
       \strut\cr\hbox{\ruseng{���������, ���������}{Pavements, colorings}}\cr
                \hbox{\ruseng{� ��������� ������}{and tiling groups}}\cr}}}


\rus
{\centering \bf �.�.�����-������, �.������-��������, �.��������,\goodbreak �.����������, �.���������\endgraf}

\eng
{\centering \bf A.Belov-Kanel, I.Ivanov-Pogodaev, A.Malistov,\goodbreak I.Mitrofanov, M.Kharitonov \endgraf}

\rus
������ ��������� ����� ����� ���������� � ������ ��������� ������� � ����������. ����� ����� ����� ������ �������� � ������� ���������. ����� �� ����� ���������� ������� �������� �������� ����� ������� ������, ���������� � ����������� ������� ������ �����. ������� �� ������, ��� �� ����, �������� ��������� � ����� ��������, � ����� ���������� �������, ��� ��������� ����� ���� ������� � ����� ������ �����.

\rus
������ ���� �������� ���������������, ��� ��������� ����� �� ���������. ������ � ������ ����� �������� �����������������, ��� �� ������������� ����������� ������� ������ ������. �� ������ �������� ��������� �������� ������� � ��������� ����� ���� � ����� �� ������. � ������� �� ������ �������� ������� ������ �����. � ��������� ����� �� ��������� ����� ������� �\3~��������� ����������.

\eng
The problems of tiling often act as the centre of various mathematical matters. Very often such problems are solved with the help of coloring. One of the aims of this project is to study a more powerful method related to application of the notion of the group theory. Conjointly we will explore what, in essence, is the coloring in the new terms, and will also see how the tilings could be used in the group theory.

\eng
The first cycle is preliminary, it contains a few tiling related problems. The second and the third cycles are preparatory, during those we develop the necessary technique of the new method. During the second cycle some useful terms are introduced, and the relations between the words and the paths on graphs are studied. During the third cycle we introduce the basic terms of the group theory. In the fourth cycle we employ the new technique to the tiling problems.

\rus\sect A. ��������� � ���������

\eng\sect A. Tilings and colorings

\midinsert
\hfil
\oalign{\hfil$\includegraphics{../figs/tiling.9}$\hfil\cr \strut \ruseng{������ �� 3 ������}{3-cells corners}\cr} \hfil
\oalign{\hfil$\includegraphics{../figs/tiling.10}$\hfil\cr \strut\ruseng{$L$-���������}{$L$-tetromino}\cr}
\hfil
\oalign{\hfil$\includegraphics{../figs/tiling.12}$\hfil\cr \strut\ruseng{$T$-���������}{$T$-tetromino}\cr}
\endinsert

\task A1. ��� ����� $M$ � $N$ ������������� $M{\times}N$ ����� ������� �� ������ �� ���� ������?

\task A1. Find all integers $M$ and $N$ such that a rectangle $M{\times}N$ can be cut into 3-cells corners?

\task A2. ��� ����� $M$, $N$ � $P$ ������������� $M{\times}N$ ����� ������� �� �������������� $P{\times}1$?

\task A2. Find all integers $M$, $N$, $P$ such that a rectangle $M{\times}N$ can be cut into rectangles $P{\times}1$?

\task A3. ��� ����� $M$, $N$ � $P$ ������������� $M{\times}N$ c ����� ����������� ������� ����� �������
�� �������������� $P{\times}1$?

\task A3. Find all integers $M$, $N$, $P$ such that a rectangle $M{\times}N$ with one additional cell can be cut into rectangles $P{\times}1$?

\task A4. ��� ����� $M$, $N$, $A$, $B$ ������������� $M{\times}N$ ����� ������� �� �������������� $A{\times}B$?

\task A4. Find all integers $M$, $N$, $A$, $B$ such that a rectangle $M{\times}N$ can be cut into rectangles $A{\times}B$?

\task A5. ��� ����� $M$ � $N$ ������������� $M{\times}N$ ����� ������� �� $L$-���������?

\task A5. Find all integers $M$, $N$  such that a rectangle $M{\times}N$ can be cut into $L$-tetromino?

\rus
��������� ������ �� �������� � ������� ������� ���������, ��� �� ������� ����� ����������� ����� �������� ������. ���� �� �������� � ������ $B,C,D$.

\task A6**. ��������, ��� ���� ������������� $ M {\times} N $ ����� ��������� � ������� $T$-\hskip 0pt ���������, �� $M$ � $N$ ������� �� $4$ .

\eng
The following problem cannot be solved by colorings. We should develop some more powerful ideas to solve it. We shall do this in sections $B,C,D$.

\task A6**. Suppose that $M  {\times} N$ rectangle can be tiled by $T$-tetramino. Prove that $M$ and $N$ are divisible by $4$.

\rus\sect B. ���������������� ��������: �����, ����� � ����

\eng\sect B. Spade-work: words, graphs and paths

\rus
����� ���� ��������� �������� ������� $A$: ��������� ���� {\boldmath $a$,\1~$b$,\1~$c$,\1~$\dots$ 
�� ���� �������� ����� ���������� �����~--- �������� ������������������ ����, ��������, 
$abbc$, $c$, $cabcabccbb$ � �.�.} 
����� �������� {\it �������������} ���� $A$ �~$B$ �����, ������������ ������������� ����� $B$ ������ � ����� $A$. ����� �������, ������� ������ ��������� ����, � ������������ �� ��� ��������� ������������. 

\eng
Let an alphabet $A$ be a set of letters $a$,\1~$b$,\1~$c$,\1~$\dots$.
We can use these letters to arrange words which are finite sequences of these letters, for example, $abbc$, $c$, $cabcabccbb$ etc.
A word is called {\it product} of two words $A$ and~$B$ if it is congruent with the word $AB$ ($B$ attached to the right of $A$). Hence, an alphabet determines the set of words with product operation.

\rus
{\it {\normalmath $N$}-�� ��������} ����� $X$ ���������� �����, ������������ ������������ �����~$X$ {\normalmath $N$}~��� ������.

\task B1. ��������, ��� ���� ������������ ���� $U$ � $V$ ��������� �  ������������� ���� $V$ �~$U$, �� �~$U$, �~$V$ �������������� � ���� �������� ������-�� ����� $A$.

\eng
A word written $N$ times in a row ($\underbrace{XX \dots XX}_{N {\ \rm times}}$) is called {\it {\normalmath $N$}-power} of $X$ and is denoted by $X^N$.

\task B1. Suppose that the product $UV$ is congruent to the product $VU$. Prove that the words $U$ and $V$ are powers of some word $A$.

%%%%%%%%%  
\boldmath 
%%%%%%%%%

\rus
{\it �����������} ����� �������� ��������� ��������� � �������� �� ��� ��������� 
������������ $*$ (����������� ���������� �������� ��� ���� ��������� ��������
������� �� ���� �� ���������) � ����������� ��� ����� ��������� $a$,\1~$b$,\1~$c$ 
��������� $a*(b*c)=(a*b)*c$. ��� �������� ���������� ��������� ���������������.

\rus
\quote
{\bf �������.} ��������� ����������� ����� �������� ����������, ������������ ��������. ��������� ������������ ����� �������� ���������� ������������ ���������, �~������������ �������~--- ���, ��� ��� �� ���� ������ ������.
\endquote

\rus
���������� ��������� ��������� ���� �������� ����������� ������������ �������� ������������ ������ ����� � �������. (���������������, ��������, �����������.) 
����� �����, ����� ��������� ���������� {\it ���������} �����������.

\eng
Consider a set of elements with some product operation $*$ (the product of two elements of the set also belongs to the set). This set is called a {\it semigroup} with respect to the $*$ operation if $a*(b*c)=(a*b)*c $~ holds for all elements $a$,\1~$b$,\1~$c$. This is {\it associative} property.

\eng
\quote
{\bf Examples.} The set of integers is a semigroup with respect to the sum operation. The set of rational numbers is a semigroup with respect to the product operation. In this example we cannot change product by division because of that we cannot divide by zero.  
\endquote

\eng
The set of words determined by an alphabet is a semigroup with respect to the operation of attaching of one word to another. (It is clear that associative property holds.) More precisely, it is called {\it free} semigroup.

\task B2. ���� � ���� ���������� ��������� ����� ��������� ����� $a, b, c, d, e, f$. � ����� ����� ����� ���������� ����� �� ���� ��� ����� ������� ���� (� ����� �������): $a$ �~$b$, $c$ �~$d$, $e$ �~$f$. ����� ����� �������� ����� �� ���� ��� ���� � ����� ����� �����. ��������, ����� $\bfit dacdbeaaf$ ����� ������������� ��������� �������: 
$\bfit dacdbeaaf\hm\rightarrow dabeaaf \hm\rightarrow deaaf \hm\rightarrow dfeeaaf$. 
��������, ��� ������ ����� ����� ������ ���������� �������� � ����, ����������� ����������� ����� ����, � ���� ��� �� ������� �� ����, ����� �������� � � ����� ������� �����������.

\task B2. Peter and John assembly various words using the letters $a, b, c, d, e, f$. One can delete any of the neighboring pairs (any order) $a$ and~$b$, $c$ and~$d$, $e$ and~$f$ from any word. Also, one can add any of these pairs into any part of any word. For example, we can transform the word $\bfit dacdbeaaf$  
by the following way: 
$\bfit dacdbeaaf\hm\rightarrow dabeaaf \hm\rightarrow deaaf \hm\rightarrow dfeeaaf$.
Prove that any word can be transformed to the form containing the minimal number of letters. Prove that this form doesn't depend on a set of operations applied.  

\boldmath

\rus
���������� ������������ ��������. ��������� ������� �� ��� �������, ����� ��������� ����� �� ������� ������� ��� ������ ������� �������. ���������� ������� �������� ����� (������������������ ����), ��� ����� �������� <<�����>>, <<����>>, <<������>>, <<�����>> �������� ����� $U$, $D$, $R$, $L$ c�������������. 
��� ���� ������������������ ���� � ����� ������ ��������������� ������������������ ������� �� �������.
����� �������, ������� �������� ����� ��������������� ��������� ����, ������������ ���� �� ����� � ��������� ��\1~������������ ������.

\eng
Consider a polimino. Let us mark the edges on the boundary of this polimino with arrows placed clockwise (together) or counter-clockwise. Let us associate any polimino with the sequence of the letters on its boundary. For ``up'', ``down'', ``right'', ``left'' arrows we shall accordingly write $U$, $D$, $R$, $L$ letters. At the same time, the sequence of the letters in the word must correspond to the sequence of boundary arrows. Hence, there are several words correspond to each polimino. They can be transformed one to another by the cyclic shift.   


\midinsert
\hfil
\oalign{\hfil$\includegraphics{../figs/tiling.7}$\hfil\cr \strut $\it RRULULDD$ \cr}
\hfil 
\oalign{\hfil$\includegraphics{../figs/tiling.8}$\hfil\cr \strut $\it LULDDRRU$ \cr}
\par
\figure{}
\endinsert

\task B3. ������� ��������� ����, ��������������� ������ �� ���� ������ � �������-\hskip 0pt ������ �� ���� ������ � ��������� ���������� ���� ������ �� ��������� ���������.

\task B3. Describe the set of words corresponding to two-cells domino and three-cells corner trimino. (You should take into account various placements of the poliminoes on the plane.)

\task B4. ����� $M$~---  ��������� ����, ��������������� ��������� ���������� ������ �� ���� ������. ����� � ������ ������ �� $M$ ����� ��������� ��������� ��������: 
\hfil\break \indent
1. �������� ��� ������ ����� ������� ���� $R$ �~$L$ ��� $U$ �~$D$ (��� � ������ B2);
\hfil\break \indent
2. ��������� � ������ ����� ����� $R$, � � �����~--- ����� $L$, ��� ��������;
\hfil\break \indent
3. ��������� � ������ ����� ����� $U$, � � �����~--- ����� $D$, ��� ��������;
\hfil\break \indent
4. ����������� ���� � ����� �����, ������������ ��� ����� ���������������. 
\hfil\break
��������, ��� ����� ������ ������, ����������� �� ������, ����� �������� ��� ������ ���� ��������������. 

\task B4. Let $M$ be the set of words corresponding to the various placements of the two-cells domino on the plane. Suppose that we can apply the following operations to any word in $M$:
\hfil\break
1. Add or delete neighboring pairs $R$ and~$L$ ��� $U$ and~$D$ (in any order, as in B2);
\hfil\break
2. Add $R$ letter to the beginning of the word and $L$ letter to the end of the word (and vice versa);
\hfil\break
3. Add $U$ letter to the beginning of the word and $D$ letter to the end of the word (and vice versa);
\break
4. Attach obtained words to each other.
\endgraf
Let some region can be tiled by dominoes. Prove that the word corresponding to the boundary can be obtained by complex of these operations.


\rus
����� ��������, ���: 
�������� $1$ ������������� ���������� ��� �������� ���� ����� <<����-�������>>, 
�������� $2$ � $3$ ������������� ����������� �������� ����� �� ��� ����������� �����, � �������� $4$ ������������� ������������� �������� ���� � ����� (c ������ ����, ��� ����� ������ ����� ����� <<����-�������>>).  
%
��� ��������� �������������� ����������� ������� ��������� � �������� ������������ ����.

\eng
It is easy to see that:
%
operation~1 corresponds to adding or deleting of pair of <<there and back again>> paths;
%
operation 2 and~3  corresponds to the changing word by its cyclic shift;
%
operation~4 corresponds to the attaching words to each other (using the fact that we can delete <<there and back again>> paths).
%
Thus, we can formulate the necessary tiling condition using our language of word products.


\task B5. ����� �������� ��������� �������� �������� ������� ������� �������� $T$. ���������� ��������� ����� ����, ��������������� ������ $T$. ��������, ��� ����� �����, ��������������� ������� �������,  �������������� ��� ��������� ���������� � ����� ���������� ������ ���������� �������� ������������ � ������ ����� �� ��� ����������� �����.

\task B5. Suppose that we can tile the fixed finite region using the set of poliminoes $T$. Consider the original set of words corresponding to $T$. Prove that the word corresponding to the boundary is presented by the result of the several product and cyclic-shift operations.


\task B6. ��������� ������, ����� ����� ������� ���������� � ���������� ���������� �������� �� $B5$, ��~��������� ����������.

\task B6. Construct an example of the region which boundary can be obtained by the operations of $B5$, but tiling cannot be done.

\rus
����� ������ �� ��������� ���� �������������, �������� �� {\normalmath$N$} ��������� ��������������� ���, ��� ������� ������� �������������� ��������� �� ����� ������ ������� ������� ��������������. ���������� ��������� ����, ������������ �����, ���������� �� �������� ��������� ���������������. ����� �������, ��� �� ���������� ����� <<����-�������>> ���� �� ��������. ������� �����-������ ������� ��������� (������� ������ �� ���������������) � ����� $A$. ������������� ���� ����� ����� ������� ����� ����, ������������, ���� ������� ������ ������ <<�����������>>, � ����� ������.

\eng
Consider a polygon on the plane. Suppose that it is cut on  {\normalmath$N$} small polygons such that none of vertices of the small polygons belong to the inner part of other polygon edge. Consider closed paths of arbitrary length passing through the small polygons edges. Suppose that adding (or delete) the ``there and back'' edges doesn�t change any path. Let point $A$ be some vertex of a small polygon. 
If the path can be presented by pass through one path then do through the second one, then we say that our path is a product of two passed paths. 

\task B7. ���������� ����������� ��������� ��������� ����� ������������ � ��������������� � ����� $A$. ��������, ��� ���� �������� ����� $P$ ��������� �����, ������������ � ��������������� � ����� $A$ �  �����, ��� ����� ��������� ����, ���������� ����� $A$  ���������� � ���� ������������ ��������� ����� ����� �� $P$. ������� ����������� ����� ����� � ����� ������ $P$.

\task B7. Consider an infinite set of closed paths that start at point $A$. Prove that there exists a finite set $P$ of closed paths from $A$ such that any closed path starting at $A$ can be presented by the finite product of the paths from $P$. Find the minimal number of paths in the set $P$.


\task B8. ������� ������ ������� $B$, ���������� ��������� ����, ������������ � ��������������� � $B$. ��������, ��� ����� ���������� ������������, ����� ���: 
\endgraf
1. ������� ���� ����� $A$ ����� ��������������� ���� ���� ����� $B$ � ��������; 
\endgraf
2. ������������ ���� ����� �� $A$ ����� ��������������� ����, ���������� ������������� ��������������� ���� ������������ ����� �� $B$.

\task B8. Choose another vertex $B$. Consider closed paths starting at $B$.
Prove that we can provide a correspondence such that the following properties hold:
\endgraf
1. Every path starting at $A$ corresponds to its own path staring at $B$.
\endgraf 
2. If paths $p_1$ and $p_2$ starting at $A$ correspond to the paths $p_1'$ and~$p_2'$, then product $p_1p_2$ corresponds to the path $p_1�p_2�$.





\rus\sect �. ������

\eng\sect C. Groups

\rus
{\it �������} ����� �������� ��������� ��������� �~�������� �� ��� ��������� ������������~$*$, ��������������� ��������� ���������:

\rus
{
\leftskip \parindent \parindent -1.2em \advance \leftskip by -\parindent
1.\enskip {\bf ���������������.} ��� ���� $a$, $b$, $c$ ��������� $a*(b*c)=(a*b)*c$.
\endgraf
2.\enskip {\bf ������������� �������.} ���������� ������� $e$ �����, ��� $ae=ea=a$ ��������� ��� ����~$a$.
\endgraf
3.\enskip {\bf ������������� ��������� ��������.} ��� ������ $a$ c��������� ������� $a^{-1}$, ����� ��� $aa^{-1}\hm=a^{-1}a \hm=e$.
\endgraf
}

\eng
A set with respect to the product operation $*$ is called {\it a group} if the following conditions hold: 

\eng
{
\leftskip \parindent \parindent -1.2em \advance \leftskip by -\parindent
1.\enskip Associative property. For any $a$, $b$, $c$ holds $a*(b*c)=(a*b)*c$.
\endgraf
2.\enskip The existence of the unit element. There exists an element $e$ such that the equality $ae=ea=a$ holds for any $a$ in the group.
\endgraf
3.\enskip The existence of the inverse element. For any $a$ in the group there exists an element $a^{-1}$ such that $aa^{-1}=a^{-1}a=e$.
\endgraf
}

\rus
\quote \normalmath
{\bf �������.} ��������� ����� ����� �������� ������ ������������ ��������, �������� ��������� �������� ��������������� �� �����. 
��������� ������������ ����� (�� ��� ����) �������� ������ ������������ ���������. 
%
\endgraf
%
{\bf ������ �����������.}
��� �������� ����� ����������� ���� �� ������ ������ ���������� ���������: 
$213$,\1~$321$,\1~$132$,\1~$312$,\1~$231$,\1~$123$. ����������, ���� ���� �~��������������� ���� ���������: ����� �������� ������� ��� �� ��� (��������� $213$,\1~$321$\1~���\1~$132$), � ����� �������� ��� ��� �� ����� (��������� $312$ ��� $231$). ����� ����� ������ �� ������, ����� ��������� $123$. ��\2~����, �~��� ���������� ��� �� ����� ��������� <<��������>>. ���� ��������� ������� ���� ����� ��������, � ����� � ������, ����������� ����� ����� �����-�� �������� �� ���� �����. ��������, ���� ������� �������� ������� ������ ��� ��������, � ����� �������� ��� �� ����� ������ �� ���� �������, �� ���������
$123\rightarrow 213\rightarrow 321$. ��\2~����, ��� �����, ��� �������� ������� ������ � ������ ��������. ��� <<��������>> ���������� {\it �������������}. ��� �������� ������ ������������ �������� ����������������� ����������. �\3~���� ������ ����� ���������, �������� �������� ������������� �������������� $123$.
��� ����������� ������, ��� ���� �������� $a$ � $b$, ����� ��� $ab\ne ba$. ����� ������������� ������ ����������� $S_n$ ��� ������ ����������� $n$.
\endquote

\eng
\quote \normalmath
{\bf Examples.} The set of integers is a group with respect to the sum operation. An opposite number is an inverse element. The set of rational numbers (without zero) is a group with respect to the product operation.
%
\endgraf
%
{\bf Substitution groups.}
There are six ways to place three elements in the row:  $213$,\1~$321$,\1~$132$,\1~$312$,\1~$231$,\1~$123$. In fact, we consider the transformations of the three elements: we can interchange two of them (so we obtain $213$,\1~$321$\1~or\1~$132$), or we can shift all three elements by the cycle (so we obtain $312$ or $231$). Also we can do nothing so we stay with $123$ in this case. It is easy to see that we have six different <<actions>>. If we apply one of these actions and immediately another one, then we obtain the action from the six ones again. For example, if we interchange the first two elements and shift all three elements by the cycle to the right, then we obtain
$123\rightarrow 213\rightarrow 321$. Thus, we obtain the action of interchanging
of the first and third elements. These <<actions>> are called {\it substitutions}. The set of substitutions is a group with respect to the consecutive applying operation. There are six elements in this group. The identical transformation $123$ is the unit element. This group is the smallest group such that there holds $ab\ne ba$ for some $a$ and $b$. We denote it by $S_3$. We can consider substitution group $S_n$ for any integer $n$.
\endquote





\task C0. ���������, ��� ���� �� ����� B8 � B9 �������� ������.

\task C0. Check that paths in the B8 and B9 form a group. 

\rus ������ ���������� {\it a�������} ��� {\it �������������} ���� ��� ����� ��������� $a$, $b$ ��������� $ab=ba$.

\eng A group is called {\it abelian} or {\it commutative} if $ab=ba$ holds for any $a$ and~$b$.

\task C1. ��������� ��������������� ������ �� $8$ ���������.

\task C1. Construct a nonabelian group consisting of $8$ elements.

\task C2. ��������, ��� ��������� �������� � ������������, ����������� ��� �\3~����, �������� ������. ������� ����� �� ���������.

\task C2. Prove that the set of motions in space that transfer the cube to itself is a group. Find the number of elements in this group.


\task C3. ��������, ��� ��������� ���� � �������� $\{a_1$, ${a_1}^{-1}$, $a_2$, ${a_2}^{-1}$, $\dots$, $a_n$, ${a_n}^{-1} \}$
�������� ������ ������������ �������� ������������ (� ����������� ����� ������� �������� ���� $x$ �~$x^{-1}$).

\rus
����� $G$~--- ������. {\it ����������} ���������� ������������ $H\in G$ ��������� ������, �����, ��� ���� $a$, $b$ ����� � $H$, �� $a^{-1}$, $b^{-1}$,~$ba$ �~$ab$ ���� ����� � $H$. ��������� ���� �� ���� ���� �������� �������, � ��� �� ���������. 

\task C3. Prove that the set of words in the alphabet $\{a_1$, ${a_1}^{-1}$, $a_2$, ${a_2}^{-1}$, $\dots$, $a_n$, ${a_n}^{-1} \}$ is a group with respect to the attaching operation. (Also we can use cancellation of neighboring inverse letters  $x$ and $x^{-1}$.)

\eng
Let $G$ be a group. Suppose that $H$ is a subset of $G$ and if $a, b \in H$, then $a^{-1}, b^{-1}, ba, ab \in H$. Then we say that $H$ is {\it a subgroup} of $G$. $H$ is a group too, with respect to the same operation.


\task C4. ��������, ��� ������ ������� � ������ ����������� $S_n$ ���� ������������ ���������� ����������� ������. ������� ��� ��������� ������ ����������� �� ���� ���������.

\task C4. Prove that every element in the substitution group $S_n$ is a product of several independent cycles. Describe all subgroups in the substitution group $S_5$.

\rus
�������� $a$ � $b$ ���������� {\it ������������}, ���� c��������� ����� �������~$x$, ��� $xax^{-1}=b$. 
���� $H$~--- ��������� ��������� ������ $G$,
�� ����������� ��������� $xHx^{-1}$ ����� �������� ��������� $G$, 
��� ��� $xh_1x^{-1} xh_2x^{-1} \hm= xh_1h_2x^{-1}$.

\eng
Elements $a$ and $b$ are called {\it conjugate} if there exists an element~$x$, such that $xax^{-1}=b$. If  $H$~is a subgroup, then {\it conjugate set}  $xHx^{-1}$ is also a subgroup, because of $xh_1x^{-1} xh_2x^{-1} = xh_1h_2x^{-1}$.

\task C5. ������� ��� ����������� ��������� � ������ ����������� �� ���� ���������. 

\task C5. Find all conjugate subgroups in the $S_5$ substitution group.



\rus
����� ���� � �� �� ������ ����� ���� ������� ���������� ���������. ��������, ���������� ������ ����� ���� ��������, ����������� ������������ � ���� ��� ����������� �� ���������� ���������, ��� ���� ���� ���������� ������ ����� ����������. ��� �������� <<������������>> ���������� ����������� �������.

\rus
������ $G$ � $H$ ���������� {\it �����������}, ���� ����� �� ���������� ����� �������� ������������, ���������� ���������� ����������:
\endgraf
1. ��� ������� �������� �� $G$ ���������� ������������ ��������������� ��� ������� �� $H$, � ��������.
\endgraf
2. ���� $g_1, g_2\in G$ ������������� $h_1, h_2\in H$, �� $g_1g_2$ ������������� $h_1h_2$.

\eng
A group often can be described by different methods. For example, elements of a group can be presented by the motions in space transferring polyhedron to itself, or by substitutions of several elements. The structure of a group be the same. There is a special notion to describe the <<sameness>> idea.

\eng
Groups $G$ and $H$ are called {\it isomorphic} if there exists a correspondence between $G$ and $H$ with the following properties:
\endgraf
1. There is an unique element $h\in H$ corresponding to any element $g\in G$, and vice versa;
\endgraf
2. If elements $h_1,h_2 \in H$ correspond to the elements $g_1,g_2 \in G$, then product $h_1h_2$ corresponds to $g_1g_2$.


\task C6. ������� ������ �����������, ���������� ������ ��������, ����������� ���.

\task C6. Suppose that $G$ is a group of motions transferring the fixed cube to itself. Find a substitution group which isomorphic to $G$.


\rus
����� �������� ��������� ������ ���������� � ��������� ������ ���, ��� ���� ������������ ���� ��������� ������� ������ �� ������ ������������ � �� ������� �� ������ �������� ������ �����. �� ���� ������������ ��������� � ������� 1 � 2 ������ ����� ���� � ��� �� ����, ���������� �� ����, ����� �������� � ������� 1 � 2 �������.

\eng
Suppose that the elements of a group are colored in several colors such that the color of product depends on colors of the elements only and not depends on the choose of elements of that color. Hence, the product of elements colored in 1 and 2 colors always has the same color (we can take any elements with color 1 and~2).  


\task C7. ��������, ��� ��������� ��������� � ������, ��� � �������, �������� ���������. ����� ��������� ���������� {\it ����������}.

\task C7. Prove that the set of all elements having the same color as unit element is a subgroup. This subgroup is called {\it normal}.

\rus
{\bf ������������� �����������.} ��������� $H\in G$ ���������� {\it ����������}, ���� ��� ������ �������� $g\in G$ (�� ����������� �������������� $H$)
��������� $gHg^{-1}\in H$. �� ����, ���������� ��������� ��������� ���� ����.

\eng
{\bf Equivalent definition.} A subgroup $H\in G$ is called {\it normal} if for any $g\in G$ ($g$ may be not in $H$) the following holds: $gHg^{-1}\in H$. In other words, a normal subgroup is conjugate to itself.


\task C8. �������� ��������������� �����������.

\task C8. Prove this equivalence of the definitions.

\task C9. ������� ��� ���������� ��������� � ������ ����������� $S_4$.

\task C9. Find all normal subgroups in the substitution group $S_4$.

\task C10. ���������� ��������� ������ $G$. ����� $K$ ��������� ��������� ���� $aba^{-1}b^{-1}$ (��� ���������� {\it �����������}). ����� $H$~--- ��� ������������ ������������ ��������� �� $K$. ��������, ��� $H$ �������� ���������� ����������. 

\task C10. Consider a group $G$. Let $K$ be a set of elements $aba^{-1}b^{-1}$. (they are called {\it commutators}). Suppose that $H$~is the set of all possible products of elements in $K$. Prove that $H$ is a normal subgroup. 



\rus\sect D. ��������� ������

\eng\sect D. Tiling groups

\rus
��������� ������ �� ���������� ������� ����� �������� {\it �������}, ���� �� ����� ��� ������ � ����� ������ ����� �������, �������� �� ������ � ������ �� �������.

\rus
����� $T$~--- ��������� ������ �� ���������� �������, ���������� � �������� ������. ���� �������� $T$ ����� ������, �� ������� �� ������ 
����� ������, ����� �������� $T$ {\it �������}. ������ �� ����� ������������� ��������� � ������� ������.

\rus
���������� ��������� ����, ��������������� ��������� ������ ������. ����� � ���� ���������� ����� ������ � ����, ��� � ������ B4, �� ���� ����� �����, ����������� � ����� ����� �������������� �����, �������� ����� �� ��� �����������, � ����� ����������� ����� ��� ������������ ����� (�� ���� ����� ������������ ����). 

\task D1. ��������, ��� ���������� ��������� ������� ����� �������� ������.

\rus
����� �������� ��� ������ {\it ��������� �������} ������� ������. 

\eng
A set of cells on the square lattice is called {\it connected} if we can walk from any cell to another by passing thought cell edges. 

\eng
Let $T$ be a set of cells on the square lattice. Suppose that $T$ have connected complement set. If we can walk through the boundary of $T$ passing all the edges one time only, then we say that $T$ is a {\it tile}. Now we shall consider the pavements with tiles. 

\eng
Consider a set of words corresponding to the finite tile set. Let us play with this set the game as in B4 problem: add or delete pairs of inverse letters, or change word by its conjugate, or attach words to each other (take words products).

\task D1. Prove that the set of all words that we obtain by such operations is a group with respect to the product.

\eng
This group is called {\it a tiling group} of the given tile set.


\task D2. ����� $C$~--- ��������� ��������� ����� ��\2~���������� �������. 
��������, ��� ��������� ��������������� ���� ����� ���� �������� ������. ����� ��������, ��� ��� ������ ������ ��������� ������ �������� ���������� ���������� �\3~������ $C$.

\task D2. Let  $C$~be a set of all closed paths on the square lattice. Prove that the set of words corresponding to these paths is a group. Prove that for any tile set a tiling group is a normal subgroup in $C$ group.


\task D3. ��������, ��� ���� �������~$O$ ���������� �������~$T$, �� �����~$dO$, ��������������� ���������~$O$, ����� �\3~��������� ������~$T$.

\task D3. Suppose that region $O$ can be tiled by tile set $T$. Prove that the word $dO$ corresponding to the boundary of $O$ is in the tiling group of $T$.









\bye


\task C9. ���������� ��������������� ����, ���� �������� ��������� � ��� �����, � ������ ������� ������ ������� � ����� �����, � ������� ����� �� ������. ��������������� ����� ���������� �������, ������� ������������ ������ ������� ����� �����-�� ������ �������, ��� ���� ��� ����� ������� ���� ������������ ��������. ����� ��� ����� ���� ������ ���� �������������� �����, ����������� ���������� � ����� ����, ����������� ������ ������� �� ������.  
���� �� ������� ������ ��� ���� �� ����� �������, � ����� - ��� ���� �� �������, �� �� ����� ���� ��, ���� ������ ��, ������ ��� ���� �� �������, � ����� - ��� ���� �� �����. ��������, ��� ��� ������ ����� "���" �� "�������� ������" ���� ��������� ������.


��������, ��� ������ ��������� � �������� �����. ������, ����� ������� � ���������, ���� ���� � ���, ��� ������ ������ �������������
������������ ����� ��� �����, ����� ���� ������� ������� �����/������ �������� � ��������, ��\2~������� ���� ��������� �������.
����� ����� ����������� ��������� ����������� ��� ����������� ��������� ��������� ����� � ������� ������� �����/������ ��� �������� 
���������. ����������, �������� ����������� ��������� �� ��������� � ����� ������� �������, ����� ��������� ����������, ����� �� 
��������� ��������� ����� �� �������� ���������.

����������, �� ����� ����������� ������� �������� ������ $C$ ��������� ������� ������, �������� � ����� ������� ������ $G$ ���, ����� ������������ ��������� � $C$ ��������������� ������������ � $G$. ����� ������ ������ ����� �������� �����-�� ������� � $G$, � ��������� ������~--- �����-�� ��������� � $G$. 

\task D4. ����� ������������ ������������ ��� ��������� ���������?

\task D5. ����� $\phi$~--- ������������, ��� ������� ������ ����������� �� $4$ ��������� ����������� ������� ������ $G$, � ������� ��������� ������, 
��� � ������ ����������� �� $4$ ���������. ��� ���� $\phi(xy)=\phi(x) \phi(y)$ 
(������������ ����������� ������������� ������������ � $G$ ������� ������������).
����� ��������� ����������� ����� ��� ���� ���������� � ������� ������ $G$?

\task D6. ��������, ��� ��� ������������, ����������� ������������ � ������������, ��������� ���������, ����������� � ������� ������ �������� 
���������� ����������.

\task D7. ����� $\phi$~--- ��������� ���������, �������������� ��������� ������ $C$ �������� �����-�� ������ �������� ������ $G$, �����, ��� 
$\phi(xy)=\phi(x) \phi(y)$. ������� ��������� � $C$, ������� ��� ��������� � ������� ������ $G$.

\task D8. ����� $F$~--- ������ ������������ ����� �� ���������� �������. ��������, ��� $C$ (������ ��������� �����) ����������� ����������
���� $aba^{-1}b^{-1}$, ��� $a,b\in F$. 

\task D9. ����� ��, ��� ���������� ���������, ���������� ��� ������ ���������?

\task D10. ����� �� �������� ��������� ������� $R$ � ������� ������ ������ $T$. ����� ��, ��� ���� ��������� ����������, �� ���������� ���������, 
������������ ���? 
 


\bye
