%&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}}}


\count0 5
\figurec 1
\def\taskstyle{\rm}

\def\hline#1{\noalign{\hrule height #1}}
\def\xvrule{\vrule width 1.2pt }
\def\recty#1#2#3{\vcenter{\halign{\xvrule##&&\hbox to #1{\hfil}%
     \xvrule height #1 ##\cr
\hline{1.2pt}
&width #2 &\cr\hline{#3}
&width #2 &\cr\hline{1.2pt}
}}}

\task E1. ������������� $m {\times} n$ ������ �� ������.
    ���������, ��� �����-�� ��� ������ �������� ������� $2{\times} 2$.
\endgraf
a) ������ ����������� ��������� ���������� ����� �����������?
\endgraf
    b) ���������� ������� $2{\times} 2$ �� �����-�� 2 ������.
    � ���� ����������� ������ ��������������
    (Flip), ����������� ������������ ��� ��������� �
    �������������� � ��������. ��������, ��� � ������� ������� �����
    �������������� ����� ��������� ����� ��������� � �����.
$$
\recty{10pt}{1.2pt}{.3pt}
\quad \longleftrightarrow \quad
\recty{10pt}{.3pt}{1.2pt}
$$
\figure{}
\endgraf
{\it �������� � �������.} �������������� ���������� �� ��������. ����� ������������ ������� �������������� ������ �����. ���� ������: ��������� ��� ��������� �����������. 
    c*) �� ����� ���������� ��������� ���������� ����� ��������������
����� ��������� ����� ��������� � �����?

\task E1. Consider a rectangle $m {\times} n$ tiled by dominoes. Check that
there exists a subsquare $2{\times} 2$ consisting of two dominoes.
\endgraf
a) Find the minimal number of these subsquares.
\endgraf
b) Consider a square $2{\times} 2$ tiled by 2 dominoes. Let us define
a {\it flip}: it is a transformation of a horizontal tiling to a vertical one and vice versa.
Prove that for any tiling of an $m {\times} n$ rectangle there exists a sequence of such flips such that we can
obtain any other tiling.
$$
\recty{10pt}{1.2pt}{.3pt}
\quad \longleftrightarrow \quad
\recty{10pt}{.3pt}{1.2pt}
$$
\figure{}
\endgraf
   c*) Find the minimal number of flips which is sufficient for transforming of any tiling to any other one.

\rus
{\bf �����������. } � ���������� �� ��� ���������� � �����
����������������. ������ �� {\it �������.\/} ����~--- ��� �����
��������������, ��� ������� ���������� ����� ���������
������������ ���� � �������� ����������� ������ �� ���.

\eng
{\bf Definition. } Below we shall examine these flip transformations.
To make a flip, we choose the region in the plane of fixed form and change the tiling into it.


\task E2.
    ������������� $m\times n$ ������ �� ������ $1{\times}k$.
    ���������, ��� �����-�� $k$ �� ��� �������� ������� $k{\times} k$.
\endgraf
a) ������ ����������� ��������� ���������� ����� �����������?
\endgraf
    b) ����� ������������� ������ �� ������ $1{\times}k$ � ����� �����-�� $k$
    �������� ������� $k{\times} k$. ����������, �\3~���� ����������� ������ ��������������
    (Flip), ����������� ������������ ��� ��������� �
    �������������� � ��������. ��������, ��� � ������� ������� �����
    �������������� ����� ��������� ����� ��������� � �����.
\endgraf
{\it �������� � �������.} ���������� E1b.
\endgraf
    c*) �� ����� ���������� ��������� ���������� ����� ��������������
����� ��������� ����� ��������� � �����?

\task E2. Consider a rectangle $m {\times} n$ tiled by $1{\times}k$ tiles. Check that
there exists a square $k{\times} k$ consisting of k $1{\times}k$ tiles.
\endgraf
a)  Find the minimal number of these squares.
\endgraf
b)  Consider a rectangle $k{\times} k$ tiled by $1{\times}k$ tiles.
Similarly, a {\it flip\/} is a transformation of a horizontal tiling to a vertical one and vice versa.
Prove that for any tiling of an $m {\times} n$ rectangle there exists a sequence of such flips such that we can
obtain any other tiling.
\endgraf
 c*) Find the minimal number of flips which is sufficient for transforming of any tiling to any other one.

\midinsert
\noindent\hfil
$\vcenter{\hbox{\includegraphics{../figs/flip.1}}}$ 
$\qquad \longleftrightarrow \qquad$
$\vcenter{\hbox{\includegraphics{../figs/flip.2}}}$ 
\figure{}
\xdef\figi{\the\figurec}
\endinsert

\task E3. a) ��������, ��� ����������-������������ �������� ������������� ����������� �� ���������������. ��������
    ��������, �.�. ��� ���� �������� ������������� ����������� �� ���������������, �� �� ����������-�����������.
\endgraf
    b) ���������� ��������� ����������� $2n$-��������� � ���������� ��������� �� ����� � ���������� ���������.
���� �����-�� ��� ����� ����� �������� �������������, �� ���� ��� ��������� ����� �������� �� ������ (��.~���.~\figi), �
 ������� ��� �������������� {\it ������}. ��������, ��� � ������� ������� ������ ����� ��������� ����� ��������� � �����.
\endgraf
    c) �� ����� ���������� ��������� ���������� ������ ����� ��������� ����� ��������� � �����?
\endgraf
 d) ����� ����������� ����� ��������������� ����� ����������� ��� ��������� ����������� $2n$-��������� � ����������
��������� �� ���������������?
\endgraf
e) ���������� ��������� ����������� $6$-��������� �� ��������~$n$ �� ����� � ���������� ���������. ��������, ���
� ������� ������� ������ ����� ��������� ����� ��������� � ����� � �������, �� ����� ���������� ��������� ����������
������ ����� ��������� ����� ��������� � �����.
\endgraf
{\bf �������� � �������. } ��������� ��� $n{\times} n{\times} n$ � ���� ��������� ������. ��� ���������� � ���������, ���� �������
������� �� ������?

\task E3. a) Prove that a central-symmetric convex polygon can be tiled by parallelograms. Also prove
the converse fact that if a convex polygon can be tiled by parallelograms then it is central-symmetric.
\endgraf
b) Consider a tiling of the regular $2n$-polygon (with unit edges) by rhombuses with unit edges.
If there exist three such rhombuses forming a hexagon then we can change this tiling to another one (see picture~\figi).
We shall call this transformation a {\it flip}. Prove that it's possible to obtain any tiling by some sequence of flips.
\endgraf
c) Find the minimal number of flips sufficient for transforming of any tiling to any other one.
\endgraf
d) Find the minimal number of hexagons used in tiling of a regular $2n$-polygon (with unit edges) by parallelograms.
\endgraf
e) Consider a tiling of the regular hexagon (with edges of length $n$) by rhombuses with unit edges. 
Prove that it is possible to obtain any tiling by some sequence of flips. Find the minimal number of flips sufficient for transforming
of any tiling to any other one.
\endgraf
{\bf Note. } Draw a cube $n{\times} n{\times} n$ 
using the picture of brick arrangement. How does the picture change
when we remove the bricks one by one?

\midinsert

\tabskip 0pt plus 1000pt
\halign to \hsize{\hfil # \hfil&\hfil # \hfil\cr
$\vcenter{\hbox{\includegraphics{../figs/flip.3}}}$&%
$\vcenter{\hbox{\includegraphics{../figs/flip.5}}}$ 
$\qquad \longleftrightarrow \qquad$
$\vcenter{\hbox{\includegraphics{../figs/flip.6}}}$ \cr
\noalign{\kern 4pt}
\figure{}\xdef\figiii{\the\figurec}&%
\figure{}\xdef\figv{\the\figurec}\cr
}
\endinsert

\task E4. ���� �������� ������������� ������� �� ��������� ���������. � ���� ������� � ��������� ���� ����
����������� (��. ���.~\figiii).
\endgraf
    {\bf ������� 1.} � ������ ������� ������ �� �� ���������� ����, ��� � �������.
\endgraf

\task E4. Consider a finite rectangle grid on the square lattice.  
Suppose that any edge of this grid is oriented (see picture~\figiii).
\endgraf
    {\bf Condition 1.} For any vertex, there are equal numbers of ingoing and outgoing edges.
\endgraf

\rus
    ������� {\it ������} ��������� ��������������: ���� ��� ������� ������ ������ ���������� �� ������� �������,
�������� �� �����������, � ��������, ���� ��� ������� ������ ������ ���������� ������ ������� �������, ��������
�� �����������.
��������, ��� � ������� ������� ������ (��.~���.~\figv) ����� ������������ �������, ��������������� ������� 1,
����� ��������� � ����� ������������ �������, ��������������� ������� 1.
\endgraf
{\bf �������� � �������.} ����������� ������� $h(x)$, ���������� ��������� �������: ���
������ ������ $�$, � ������� ���� �������������� �����, $h(x)=0$. ����� ���������� $h$ ����������: ���� ���
$�$ ���������� $h(x)$, � $y$~--- �������� � $�$ ������ �� �������, �� $h(�)$ ����� 0, ���� � ������ $y$ ����
�������������� �����; 1,\3~���� ��� �������� �� $x$ � $y$ �� ���������� ������������ �����, ������ ����� �������
������������ ����������� ��������; $-1$, ���� ��� �������� �� $x$ � $y$ �� ���������� ������������ �����, ������
������ ������ ������������ ����������� ��������. �������� ���������, ��� ��� ������� ���������� ���������. 
����� ����������� ������� $A$ ���������� ����������� ������� $B$, ���� ��� ������ $x$ $h_A(x)\geq h_B(x)$. ���������� ����������� $C$ �����, ��� ���� ���� ���� ��������� � � ����������� $D$, �� $C$ �� ���������� $D$. �.�. ����������� �������� �����, ����� $C$ ����������. �������� ��������, ��� �� ���������� ����� ����� $x$ �� $C$, ��� ��� ���� ����� $y$, �������� � ��� �� �������, $h(x)\geq h(y)$. ����� $C$ ������������ ������������ �������. 

\eng
Let us call by {\it flip} the following transformation. If all the arrows around the cell are oriented clockwise, then
we change the directions of all arrows, and vice versa, if all the arrows are oriented counterclockwise, we do the same.
Suppose that condition 1 holds for the placement of the arrows. Prove that this placement can be transformed by flips
into any other placement satisfied condition 1.
\endgraf
{\bf Note.} Consider the function $h(x)$, with the following condition hold:
if cell $�$ contains nondirected edge, then $h(x)=0$. Let us define $h$ by induction: if $h(x)$ is defined for some $x$,
and $y$ is a neighboring cell (by edge), then $h(�)$ is defined in the following way:  $h(�)=0$, if the cell $y$
contains nondirected edge, $h(�)=1$, if we intersect oriented edge which goes from the left to the right, and $h(�)=-1$,
if we intersect directed edge which goes from the right  to the left. You may assume that this function is well
defined.

\midinsert
\noindent\hfil
$\vcenter{\hbox{\includegraphics{../figs/flip.4}}}$ 
\figure{}
\xdef\figiv{\the\figurec}
\endinsert

\task E5. ���������� ������������� $m{\times} n$, �������
    ��������� �������� ���������. ���������� ��������� ������������ �����
    ������ (��. ���.~\figiv).
    ��������, ��� ����� �����, ���������� �� ���������� 2 ������,
    ���������� ����� ���� ���������, � ����� $m$ � $n$ ������� �� 4.

\rus
{\it �������� � �������.} ��, ��� ����� �����, ���������� �� ���������� 2 ������, ���������� ����� ���� ���������, ������������ ��������� �� ������ ���������, ���� ���������� ���������, ������� � �������� ������ ����. ��� ��������� ��������, ��� $m$ � $n$ ������� �� 4.

\task E5. Consider a rectangle $m{\times} n$ tiled by tetraminoes. Further consider the following diagonal net
of lines (see the figure~\figiv).
    Prove that each edge containing diagonals of two cells meets just one tetramino, and that  
    $m$ and $n$ are divisible by 4.

\midinsert
\noindent\hfil
$\vcenter{\hbox{\includegraphics{../figs/flip.7}}}$ 
$\quad \mathop{\longleftrightarrow}\limits^{\rm } \quad$
$\vcenter{\hbox{\includegraphics{../figs/flip.8}}}$ 
\hfil
$\vcenter{\hbox{\includegraphics{../figs/flip.9}}}$ 
$\quad \mathop{\longleftrightarrow}\limits^{\rm } \quad$
$\vcenter{\hbox{\includegraphics{../figs/flip.10}}}$ 

\noindent\hfil
$\vcenter{\hbox{\includegraphics{../figs/flip.11}}}$ 
$\quad \mathop{\longleftrightarrow}\limits^{\rm } \quad$
$\vcenter{\hbox{\includegraphics{../figs/flip.12}}}$ 
\figure{}
\xdef\figvii{\the\figurec}
\endinsert


\task E6. ��������, ��� � ������� ������ (��.~���.~\figvii)
    ����� ��������� ����� ��������� � �����.

\rus
{\it �������� � �������.} ���������� ������������ ����� �� $�5$. �� ������ ��������� �������� ����� � �������, ��� ����� ������� ����� ���������, ����������� ��� �������. ��� ���������� ����� �� ������������ ���� �������� $E4$. 


\task E6. Prove that by sequences of flips (see the figure~\figvii)
    each dissection can be transferred into each other.

\midinsert
\noindent\hfil
$\vcenter{\hbox{\includegraphics{../figs/flip.13}}}$ 
\figure{}
\xdef\figxiii{\the\figurec}
\endinsert


\task E7. ����� ������� ������,
    ��� ����� ������ �� ���������� �� �������~\figxiii\ ���������� �� �����
    �����~������ ������, ������ �-��������. ����� $T_n$~--- ���������
    �-������, ��������� �� $n$ ������, � $|T_n|$~--- ����������
    ��������� ����� ���������.
    ������� $|T_{n}|$.
{\it �����:} $2^{n-1}.$

\task E7.  Connected  tiles such that each line indicated in the
    figure~\figxiii\
    meets not more than one of its cells, will be called {\it �-tiles.} 
    Let $T_n$~be the set of �-tiles consisting of $n$ cells, 
    and $|T_n|$~ be the number of elements in this set.
    Determine $|T_{n}|$.

\midinsert
\noindent\hfil
$\vcenter{\hbox{\includegraphics{../figs/flip.16}}}$ 
\figure{}\xdef\figxvi{\the\figurec}
\endinsert

\midinsert
\noindent\hfil
$\vcenter{\hbox{\includegraphics{../figs/flip.17}}}$ 
\figure{}\xdef\figxvii{\the\figurec}
\endinsert

\task E8. ��������, ��� ���� ������������� $a{\times}b$ ����� ������� �-��������, ����������� ��\endgraf
�)~���.~\figxvi,
b)~���.~\figxvii,
�� $10$ �����~$ab$.

\task E8. Prove that if a rectangle $a{\times}b$ can be covered by �-tiles shown at 
a)~fig.~\figxvi,
b)~fig.~\figxvii,
then $10$ divides~$ab$.


\midinsert
\tabskip 0pt plus 1000pt
\halign to \hsize{\hfil # \hfil&\hfil # \hfil\cr
$\vcenter{\hbox{\includegraphics{../figs/flip.14}}}$&%
$\vcenter{\hbox{\includegraphics{../figs/flip.15}}}$\cr
\noalign{\kern 4pt}
\figure{}\xdef\figxiv{\the\figurec}&%
\figure{}\xdef\figxv{\the\figurec}\cr
}
\endinsert

\task E9. ����� $D_n$~--- ������, ��������� �� ���.~\figxiv. ��������, ��� ���� ������ $D_n$ ����������� �-�������� �
 ���.~\figxvii, �� $n \equiv 0, 4, 15, 19\pmod {20}$.

\task E9. Let $D_n$~be  the figure indicated at fig.~\figxiv.  Prove that if the figure $D_n$ can be covered by �-tiles indicated at fig.~\figxvii\ then $n \equiv 0, 4, 15, 19\pmod {20}$.

\task E10. ������� �������� ��������� �����������
�) ������������� $2{\times}m$?
{\it �����:} $m$-�� ���� ������������������ ��������� (1, 2, 3, 5, 8...).
�) ��������� ��������� (Aztec diamond)? (��. ���.~\figxv)

\task E10. What is the number of possible tilings by dominoes for 
a) a rectangle $2{\times}m$?
b) Aztec diamond? (see fig.~\figxv)? 

\rus
��� ���������� �������� ������ $F$ � ��������� ���� �������� �� ���������� ������ $T$. ������ {\it �����������}
����� ����������� ����� � �������, ��� ����� �����, �������� ����� ������� �� ������ $T$, ������� �� $p$.
��������� {\it �����������}, ���� ����� �����, �������� ������� $F$, �� ������� �� $p$.

\eng
Consider a tiling (possibly with several layers) of a figure $F$ by tiles from some set $T$.  A distribution of numbers in cells will be called {\it an invariant} if the sum of numbers covered by any tile from the set
 $T$ is divisible by $p$.
An invariant is  {\it nontrivial} if the sum of numbers covered by $F$ is not divisible by $p$.

\task E11. a) ��������, ��� ���� ������������� ��������� ����������, �� ������ ������� $F$ �������� �� $T$ ���,
��� ��������� �������� ������ ������ �������� � 1 �� ������ ${p}$.
�) ��������, ��� ���� ������������� ����������� ���, �� ����� �������� ����������.
 
\task E11. a) Prove that if a nontrivial invariant exists then $F$ cannot be covered by tiles from $T$ so that the multiplicity of covering of each cell equals 1 modulo ${p}$.
b) Prove that if there are no nontrivial invariants then such a covering exists.

\task E12. ��� ����� $m$ � $n$ ������������� $m{\times}n$ ����� ������� �������� �� 3 ������ ���, ����� ������
������ ���� ������� ���������� ����� ���?

\task E12. For which $m$ and $n$ a rectangle $m{\times}n$ can be covered by corner triminoes so that each cell is covered by equal number of triminoes?

\task E13. {\it ���������������} ������ ����� ����������� ����� � �������, ��� ����� �����, �������� ����� �������
�� ������ $T$, �������������,
� ����� �����, �������� ������� $F$, �������������.
��������, ��� �) ���� ������������� ����������, �� ������� ������ $F$ �������� �� $T$ ���, ��� ������ ������ �������
���������� ����� ���, ������;
�)���� ��������������� ���, �� ����� �������� ����������.

\task E13. {\it A semiinvariant} is a distribution of numbers in cells, such that the sum of numbers covered by each tile from the set $T$ is negative and the sum 
of numbers covered by $F$ is positive.
Prove that  a) if a semiinvariant exists then $F$ cannot be covered by figures from $T$ so that each cell is covered by equal number of figures;
b) if there are no semiinvariants then such a covering does exist.    


\task E14. ���� ����� � ���������� � ����� � ��������. ������ ������ ��������� ����������� � ��� �������� ��
 ���������������.
�) ��������, ��� ���������� ��������� ������ �������� �������� ������.
�) ������ {\it �����������} ����� �����  ��������, ��� ����� ������ ������ ��������� ������� ����� ��������
�� ����� ������. ��������, ��� ���� ����������� ���, ��� �������� ����� �������� ��� ����������� �� ����������
���������.
�) ��������, ��� ���� ������� ��������� �� ��������� ���������� � ��������� ���������, �� ����� �����������
������� �� ���������� � �������� ���������.

\task E14. There are a board with lamps and a board with buttons. Pressing a button, we change the state of lamps connected with it, to the opposite state. 
a) Prove that the number of distributions possible for the states of lamps is a power of two.
b) A set of lamps will be called an {\it invariant} if each button changes the state of an even number of lamps in it. 
Prove that if there are no invariants then all the lamps can be switched off independently of the initial state.
c) Prove that if no invariant distinguishes the initial and the final states then a transfer from the initial state to the final state is possible.

\task E15. ������ ����� ������ {\it ������}, ���� ����� ��������� ������� ����������� ����� ��������� �������
 � ������� ������� �� ����� ������ ������.
���������� �� ����� ������, ��� �������� ������ ������� ������� ������ ������?

\task E15. A set of flips will be called {\it complete} if any pavement of the domain can be transferred to each one by some chain of flips from this set.
Is it true that for some set of tiles there exists no complete set of flips? 

\midinsert
\noindent\hfil
$\vcenter{\hbox{\includegraphics{../figs/flip.18}}}$ 
$\qquad \longleftrightarrow \qquad $
$\vcenter{\hbox{\includegraphics{../figs/flip.19}}}$ 

\figure{}
\xdef\figxvi{\the\figurec}
\endinsert


\task E16*. ������� ���� ������ �� ������� , �������������� ����� 6-���������, ������ ������� ��� ���� (����� ������� �� �������� ������ $2{\times}1$). 
� ������� ����� ��� �������, ���������� ���������. ��� ��� ������� ����� ��������������� ����������. ��� ���� ������ ������� ������������� �� ������� �������. ����������� ����� ������� �� ���� ������� 6-����������
� ������������� � ��� ������� �� �������~\figxvi. ����� ��, ��� �� ������ ������ ��������� �������� ����� ����� ��������
 ����� ������ � ������� ������� �������� ������ ������?


\task E16*.  A plane graph is dissected into domains which are hexagons with no edges inside them (we may consider them as domino tiles $2{\times}1$).  Each edge has two sides equiped by arrows. These two arrows have opposite directions and each hexagon has clockwise orientation.  It is allowed to take a domain consisting of two adjacent hexagons and change it as is indicated at the figure~\figxvi.  Is it true that every such dissection of a plane graph can be changed into each other by a chain of such flips?


