\documentclass[12pt,a4paper]{article}

\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{latexsym}
\usepackage{indentfirst} 
\usepackage{graphicx}

% \tolerance 8000


\oddsidemargin=2.0mm  \textwidth=170mm \topmargin=-5.4mm \textheight=240mm 
\advance\headsep by 6pt

\parskip=\smallskipamount


%\makeindex
\begin{document}

\def\nm{\mathversion{normal}}
\def\mychapter#1{\section*{\Large#1}}
\def\mysection#1{\par\vglue-12pt\penalty0\subsection*{\large#1}\vglue-6pt}
\def\medskip{\vskip\medskipamount}
\def\smallskip{\vskip\smallskipamount}

\def\prenum{\llap{\hbox to \parindent{$\blacklozenge$\hfil}}}

\long\def\myempty#1{}
\def\task#1{\par\smallbreak\textbf{\textbf{\prenum#1.\enspace}}\begingroup
    \sl\def\par{\endgraf\endgroup\smallbreak}\interlinepenalty9999 \ignorespaces}

\def\task#1{\textbf{\prenum#1.\enspace}\ignorespaces}


\def\ui{\fontshape{ui}\selectfont}
\let\pt\it
\def\gen<#1>{\left<#1\right>}
\def\hm#1{#1\nobreak\discretionary{}{\hbox{$\mathsurround=0pt #1$}}{}}
\def\defis{\hskip 0em\nobreak-\hskip0em }
\def\risunok{\refstepcounter{figure}рис.~\arabic{figure}}
\def\myfrac#1/#2{{}^{#1}\!/\!_{#2}}

%\setcounter{figure}{6}

%\renewcommand{\baselinestretch}{0.85}
%\renewcommand{\labelenumi}{[\theenumi]}

%\count0=12

\newbox\GGG
\setbox\GGG=\hbox{\includegraphics[scale=.3]{exlogo.2}}

\makeatletter
\def\@oddhead{\ifnum\count0>1
\vbox{\hbox to \hsize{\copy\GGG\hfil\it Группы и мозаики\hfil{\bf\Huge\the\count0}}\par\kern 6pt
\hrule
}
\fi}


\vbox to 0pt{\vss\noindent\includegraphics[scale=.7]{exlogo.2}\qquad\null\par\kern -24pt}
\hfil {\bf\LARGE Группы и мозаики}

\boldmath
\bigskip

\mysection{Решения}

\task{A1} Эта задача предлегалась на осеннем туре турнира городов в 1993 году. 

Подсчитаем двумя способами средний угол. С одной стороны, средний угол семиугольника равен $\frac{5}{7}\pi$

С другой стороны, если несколько углов сходятся во внутренней вершине, то их по крайней мере 3, и их средний угол не превосходит $\frac{2}{3}\pi$. Если же несколько углов примыкают к стороне, то ихкрайней мере 2 и соответствующий среднийугол не превосходит $\frac{\pi}{2}$

Оценим средний угол, приходящийся на вершину 1993-угольника. Сумма таких углов равна $1991\pi$, а если никакие 4 подряд идущих вершины не принадлежат одному семиугольнику, то количество примыкающих углов не менее $1993\frac{3}{2}$, потому срднийугол оказываетсяне более $\pi\frac{1991}{1993}\frac{3}{2}<\frac{3}{2}\pi$. В итоге получается, что средний угол у семиугольников меньше $\frac{2}{3}\pi$, чего не может быть.

\task{A2} а) Ответ: да, соответствующая конструкция легко строится.

б) Ответ: нет. Проходят те же рассуждения со средним углом, что и в задаче $A1$. Пусть $D$~-- диаметр семиугольника.

Рассмотрим круг с центром $O$ и радиусом $R$. Тогда  
количество семиугольников, пересекающихся с границей 
этого круга, не превосходит $4\pi DR$, а количество семиугольников, 
попавших внутрь не менее чем $\pi D(D-R)^2/S$, 
где $S$~-- площадь семиугольника.

Средний угол в семиугольнике, с одной стороны равен $\frac{5\pi}{7}$, с другой стороны, средний угол в круге не превосходит $\frac23\pi$.

Легко видеть, что граничными эффектами можно пренебречь. Подробно об этом методе см. в книге А.~Я.~Канель-Белов, А.~К.~Ковальджи "Как решают нестандартные задачи".

\task{A3} Ответ: нельзя. Проходит решение $A2$, поскольку количество семиугольников, пересечённых кругом радиуса $R$, растёт в этом случае не быстрее, чем $CR$, где $C$~-- некоторая константа.

\task{A4} Будем раасуждать, как и в предыдущих пунктах. 
Пусть $N$~-- количество углов, попавших внутрь круга радиуса $R$. 
Их среднее арифметическое не превосходит $\frac{2}{3}\pi$. С 
другой стороны, рассмотрим семиугольники 
с этими углами. Среднее арифметическое их углов равно $\frac{5}{7}\pi=
\frac{2}{3}\pi+\frac{1}{14}\pi$.

Легко видеть, что нужно добавить дополнительно более $N\frac{3}{14}$ 
дополнительных углов (если они все равны $\pi$, то ровно столько).

Таким образом, количество углов, 
попавших в полосу $R\le r\le R+1$ не менее $N\frac{3}{14}$.

Пусть $N(R)$~-- количествоуглов в круге радиуса $R$. Тогда мы имеем, что $N(R+1)>N(R)(1+\frac3{14})$

Таким образом, количество углов, попавших в круг радиуса $R$, а вместе с ним и число семиугольников, растёт экспоненциально.

\task{B1} есть легкое упражнение.

\task{B2} Ответ: $24$.

Докажем, что их не более $24$.
Будем рассматривать только положительные степени букв, 
потому что мы моеж сделать их такими, 
прибавляя к степени $a$ по $4$, к степени $b$ по $3$.
Рассмотрим следующие преобразования:
\begin{enumerate}
\item $a^4\to 1$
\item $b^3\to 1$
\item $bab\to aaa$, так как $abab=aaaa=1$
\item $aba\to bb$, так как $abab=bbb=1$
\item $aaabb\to ba$, так как $aaabb=aaaaba=ba$
\item $aabbaa\to baab$, так как $aabbaa=aaabaaa=babbbab=baab$
\end{enumerate}
Для каждого слова рассмотрим равное ему с наименьшим количеством букв $a$, среди них с наименьшим количеством букв $b$. Заметим, что каждая операция либо уменьшает первый параметр, либо уменьшает второй, не изменяя первый. Теперь посчитаем все возможные слова
\begin{enumerate}
\item $e$
\item (слова с буквы $a$): $a$~-- одно слово
\item (сочетания $ab$.) $ab\to^4 abb\to^2 abba\to^3 abbaa\to^7abbaab\to^4 abbaabb \to^2 abbaabba$. По $(3)$ слеующая буква не $b$, по $(6)$~-- не $a$. Каждый шаг однозначно определяет следующую букву, поэтому всего не более 7 слов, сочетаний $ab$.
\item (сочетание $aab$.) $aab\to^4 aabb\to^3 aabba$. Не $a$ по $(6)$, не $b$  по $(4)$. Получаем 3 слова.
\item (сочетание $aaab$.) Далее не $a$  по $(3)$, не $b$ по $(5)$. Всего одно слово.

Слова с буквы $b$:
\item $b$~-- одно слово
\item (Сочетание $ba$.) $ba\to^3baa$; $baa\to baaa\to^1 baaab$, не $a$ по $(4)$, не $b$ по $(5)$; $baa\to baab\to^4 baabb\to^7 baabba$, не $a$ по $(6)$, не $b$ по $(3)$. 7 слов.
\item (Сочетание $bba$.) $bba\to^3 bbaa\to^7bbaab$, не $a$ по $(4)$, не $b$ по $(8)$. Всего три слова.
\end{enumerate}

Мы получили такие $24$ слова, что любое другое равно одному из них.

Теперь покажем, что их не менее чем $24$.
Рассмотрим в группе $S_4$ перестановки $(1,2,3,4)$ и $(1,3,4)$.
Легко проверить, что этими двумя перестановками порождается вся группа, и соотношения для них выполнены. Это значит, что и сначала различных слов было не менее чем $24$.

\task{B3} Ясно, что при указанных преобразованиях количество букв $a$ в слове не меняется, поэтому слова с разным числом букв $a$ оказываются разными. Таким образом, количество элементов в группе бесконечно (счётно).

\task{B4} Ответ: $2n$.

Сначала покажем, что количество элементов не превосходит $2n$. Ясно, что нетсмысла рассматривать слова, содержащие подряд две буквы $a$ или две буквы $b$. Таким образом, достаточно рассмотреть множество слов $(ab)^k, (ba)^k, a(ba)^k, b(ab)^k, k<n$

Далее легко заметить, что $(ab)^k(ba)^k=e$, отсюда $(ab)^k=(ba)^{n-k}$ и $b(ab)^k=a(ba)^{n-k-1}$. Таким образом, множества $\{(ab)^k\}_{k=1}^n$ и $\{(ba)^k\}_{k=1}^n$, а также $\{b(ab)^k\}_{k=1}^n$ и $\{a(ba)^k\}_{k=1}^n$, совпадают и достаточно рассмотреть $2n$ элементов $(ab)^k$ и $b(ab)^k$.

Остаётся проверить, что группа содержит по крайней мере $2n$ элементов. Для этого рассмотрим правильный $n$-угольник. Элементом $a$ будет симметрия относительно прямой, проходящей через центр и вершину, $b$~--симметрия относительно прямой, проходящей через центр и соседнюю вершину. Легко провеить, что полученная группа удовлетворяет всем соотношениям и содержит $2n$ элементов.

\task{B9} Рассмотрим элементарные преобразования четырех типов: 

$1$ Вставка взаимнообратных букв $aa^{-1}$;

$2$ Удаление взаимнообратных букв $aa^{-1}$; 

$3$ Вставка определяющего слова $U_i$; 

$4$ Удаление определяющего слова $U_i$. 

Пусть слово $W$ выводится из пустого слова $1$ с помощью нескольких операций указанного вида. Если вывод
состоит из одной операции, то существование требуемого вида у $W$ очевидно. Пусть требуемый вид существует
у слова $W$, выводимого с помощью $N$ операций:
$$W=X_1{U_{i_1}}^{\pm 1}X_1^{-1}X_2{U_{i_2}}^{\pm 1}X_2^{-1}\dots X_k{U_{i_k}}^{\pm 1}X_k^{-1}.$$
Рассмотрим четыре случая выполнения еще одной операции--перехода к слову $W'$. Предыдущее слово $W$ представляется
в виде произведения блоков вида $XU_i^{\pm 1}X^{-1}$ для различных определяющих слов $U_i$ и сопрягающих слов $X$.
Слово $W$ получается
из такого вида сокращением некоторых подряд идущих обратных букв. Покажем как получить аналогичный вид для слова $W'$.
Последняя операция -- это вставка или удаление некоторого определяющего слова $U$ или двух обратных букв $aa^{-1}$ в
наше слово. Рассмотрим вставки. Вставка приходится либо между блоками $XU_i^{\pm 1}X^{-1}$ (очевидный случай), либо
внутрь некоторого $X$ ($X^{-1}$) либо внутрь некоторого $U_i$.
Если это вставка взаимнообратных букв $aa^{-1}$ в некоторый блок $X$, аналогичную вставку можно сделать в блок $X^{-1}$.
Получим требуемый вида у $W'$. Если же $aa^{-1}$ оказывается внутри некоторого $U$ (то есть $U=Yaa^{-1}Z$), то этот блок
 меняем на блок $XYaa^{-1}Y^{-1}YZYaa^{-1}Y^{-1}X^{-1}$. То есть получается сопряжение определяющего слова $YZ$ с
помощью $XYaa^{-1}Y^{-1}$. Пусть теперь последняя операция это вставка определяющего слова $U$.
Пусть вставка производится в какое-то слово ${U_i}^{\pm 1}$ ( то есть ${U_i}^{\pm 1}=AB$ и
${U_i}^{\pm 1}\rightarrow AUB$). Тогда блок $X{U_i}^{\pm 1}X_j^{-1}$  можно заменить на два подряд идущих блока
$XAUA^{-1}X^{-1}XABX^{-1}$ (мы вставили слово $A^{-1}X^{-1}XA$). Если же вставка производится в какое-то слово
$X$ (то есть $X=YZ$, $X\rightarrow YUZ$) то блок $XUX^{-1}$ меняем на два подряд идущих блока $YUY^{-1}YZUZ^{-1}Y^{-1}$
(мы вставили слово $YY^{-1}$).

Подобным образом разбираются случаи удаления определяющего слова или подряд идущих обратных букв (упражнение).

\task{С1} $1$. Пусть $D$ диаграмма с контуром $p$. Если клетка в диаграмме только одна, то все очевидно.
Если клеток более одной, то $D$ разрезается некоторым путем $x$ на две диаграммы с меньшим числом клеток. Пусть
$p_1x$ и $p_2x^{-1}$ контуры для этих двух диаграмм, и $p=p_1p_2$. По предположению индукции пути $p_1x$ и $p_2x^{-1}$
отвечают словам равным единице. Тогда $p=p_1p_2=p_1xx^{-1}p_2$ тоже отвечает единичному слову.
$2$. Пусть $W=1$ в $G$. Используя $B9$, представляем $W$ в виде
$$X_1{U_{i_1}}^{\pm 1}X_1^{-1}X_2{U_{i_2}}^{\pm 1}X_2^{-1}\dots X_k{U_{i_k}}^{\pm 1}X_k^{-1}.$$

$$
\vcenter{\centering\includegraphics{answers.1}\par
\risunok\label{ris:diagram}\par
}$$
Построим на плоскости ломаную $p_1$, разделим ее на отрезки и напишем на них буквы, так чтобы вдоль $p_1$ было написано
слово $X_1$. Окружность $c_1$, прикрепленную к концу ломаной разметим так, чтобы при ее обходе по часовой стрелке
читалось определяющее слово $U_{i_1}$. Чтобы получить именно дисковую диаграмму, пририсуем 0-клетки к $p_1$, $c_1$,
${c_1}^{-1}$ (см. рисунок~\ref{ris:diagram}). Получим диаграмму, по контуру которой написано слово $X_1{U_{i_1}}^{\pm 1}X_1^{-1}$.
По последнему ребру приклеим к ней аналогичную диаграмму для блока $X_2{U_{i_2}}^{\pm 1}X_2^{-1}$.
Аналогичные операции произведем со всеми блоками $X_j{U_{i_j}}^{\pm 1}X_j^{-1}$. В итоге получим диаграмму,
отвечающую слову $$X_1{U_{i_1}}^{\pm 1}X_1^{-1}X_2{U_{i_2}}^{\pm 1}X_2^{-1}\dots X_k{U_{i_k}}^{\pm 1}X_k^{-1}.$$

$$
\vcenter{\centering\includegraphics{earth.4}\par
\includegraphics{answers.3}\par
\risunok\label{ris:sokr}\par
}$$
От данного слова можно перейти к слову $W$ с помощью следующих преобразований: a) вычеркивание $1$ в некотором месте;
б) вставка $1$; в) сокращение взаимнообратных букв; г) вставка пары взаимно обратных букв. Каждое из этих преобразований
может быть проведено с помощью приклеивания нескольких 0-клеток, как показано на рисунке~\ref{ris:sokr}. В итоге получаем требуемую
диаграмму.

\task{С2} Построим вспомогательный граф $H$. Вершины $H$ выберем внутри значимых клеток (не 0-клетки)
диаграммы плюс одну вершину расположим вне диаграммы. Вершины соединим ребром, если они примыкают друг к другу
либо если могут быть соединены через цепочку 0-клеток. Вершина вне диаграммы соединяется с вершиной внутри какой-либо
клетки, если эта клетка имеет участок на контуре, либо соединяется с контуром через цепочку 0-клеток. В полученном
графе нет петель, так как все клетки отвечают циклически несократимым словам, и нет кратных ребер, так как любые
две клетки мы соединяли не более чем одним ребром. Пусть $n$ -- число вершин в графе, $r$ -- число ребер.
Из формулы Эйлера следует, что $r\leqslant 3n-6$. Теперь, в предположении, что в диаграмме нет граничных клеток,
у которых более половины периметра примыкает к контуру, докажем неравенство, противоречащее $r\leqslant 3n-6$.
Каждое ребро, соединяющее две вершины графа, находящиеся внутри клеток, разделим пополам, и будем считать, что к
двум клеткам, соответствующим этому ребру относится по половине ребра. Если ребро соединяет вершину в клетке с
вершиной вне диаграммы, то полностью отнесем это ребро к данной клетке. Таким образом, все ребра распределены.

Не граничащая с периметром клетка диаграммы соседствует не менее чем с семью другими клетками, так как каждый
участок примыкания у нее менее $1/6$ ее периметра. Значит, к такой клетке относится не менее 3,5 ребер.
Пусть клетка граничит с периметром по одной дуге. Тогда эта дуга не более половины периметра, и соседей у такой
клетки не менее $4$. Значит, к ней относится не менее $4/2+1=3$ ребер (внешнее ребро отходит к этой клетке полностью).
Если у клетки два внешних ребра, то на ее периметре чередуются участки, являющиеся контуром диаграммы и не являющиеся
таковыми. Тогда у нее, как минимум, двое соседей среди клеток и к ней относится не менее $2/2+2=3$ ребер.
Если у клетки более трех контурных участков, то к ней относится не менее 3 ребер. Итак, можно сделать вывод, что
$r\geqslant 3(n-1)$ (к вершине вне диаграммы мы ребер не относили, а к остальным отнесли, как минимум, по~3). Получаем
противоречие с $r\leqslant 3n-6$.

\task{С3} Слова $U$ и $W$ равны тогда и только тогда, когда $UW^{-1}=1$. Опишем как определить, равно ли слово $1$.
Ясно, что можно считать слово циклически несократимым. По предположению индукции можно проверить равны ли $1$ слова,
являющиеся подсловами данного. Если такие слова есть, то можно уменьшить длину исходного слова. Пусть таких слов нет.
Используя С2 заключаем, что Если в слове есть подслово $X$, такое что $XY=1$ -- определяющее соотношение и
$|X|>\frac{1}{2}|XY|$, то $X$ можно заменить на $Y^{-1}$ с понижением длины. Если же такого подслова не найдется,
то используя С2 заключаем, что для $W$ нет диаграммы, значит $W\not\equiv 1$.

\task{D1} Для решения задачи достаточно заметить, что количества букв любого сорта в периоде не зависит о того места, откуда период начинается. Поэтому, если взять отрезок периода длиной $n-1$, то из соображений баланса однозначно определена следующая буква. Поэтому, если совпадают два отрезка длиной $n-1$, то совпадают все последующие буквы. Поэтому сдвиг, переводящий одно вхождение слова $V$ в сверхслово $W$ в любое другое, кратен минимальному периоду. Поскольку $n$~--  минимальный период, это сдвиг на величину, кратную $n$.

б) Пример: рассмотрим последовательность, период которой состоит из одной единицы и двух нулей. В ней можно найти два участка $n-2$ нулей, находящихся на единичном расстоянии.

\task{D2} Пусть $n-1$~-- максимальная длина плохого слова. Ясно, что некоторое подслово длины $n$ в сверхслове $W$ повторится более чем $n$ раз. Тогда в $W$ найдётся два не пересекающихся вхождения $U$, то есть подслово $UVU$. Тогда все подслова длины $\le n$ периодической последовательности $UVUVUV\dots$ будут подсловами $UVU$, то есть подсловами $W$, то есть все они будут приличными.



\task{D3} Данная задача носит технический характер. Она давалась на основном 
туре Турнира Городов а также как один из технических пунктов на 4 летней 
конференции (задача ``слова и хаос'').

\task{D4} См. статью Самовола, Журавлева, Аннельбаума в журнале 
``Математическое просвещение'' за 2006\,г. Там эта задача разбирается. 
Решение задачи выводится с помощью очевидной индукции из следующей леммы.

 {\bf Лемма.} Дан участок длины $n+m+1$. Если символы, находящиеся на расстоянии $m$, равны, и символы, находящиеся на
расстоянии $n$, равны, то равны и символы, находящиеся на расстоянии $m-n$.

\task{D6} Достаточно показать наличие тройной развилки. Иначе подсчитаем двумя способамисредний угол наших четырёхугольников. С одной стороны, он должен быть равен $90^o$, с другой в четверной развилке он $90^o$, в развилке большего порядка - меньше. Аналогичным образом Средние углы примыкающих к стороне $90^o$, а средние углов, примыкающих к вершинам треугольника не больше $60^o$. В итоге общее среднее оказывается сторого меньше $90^o$, что и даёт нужное противоречие.

\task{D7} Делается аналогично. Если такой многогранник существует, то средний угол грани не менее $120^o$. С другой стороны, в вершине сходятся не менее трёх граней и сумма соответствующих углов строго менее $360^o$. Поэтому из оценки двумя способами среднего арифметического получаем нужное противоречие.

\task{D8} Идея решения: средний угол у грани строго меньше $120^o$.
Далее заметим, что средние углы у $k$-угольника при $k<6$ меньше $120^o$, при $k=6$ ровно $120^o$, а при $k>6$ строго больше $120^o$, причём с ростом числа сторон вклад многоугольника в средний угол растёт. В качестве оптимального достаточно взять многоугольник с $n-1$ трёх-, четырёх-, пяти-, шести-, семи-, восьми-, девятиугольниками. У любого другого средний угол будет больше. Из рассмотрения этого многогранника получаем нужное противоречие.

\task{D9} Решение команды Омска (Кудык Никита, Матвеев Константин)

 Пусть многоугольник с $S$ сторонами разбит на $n$ $k$-угольников. 
 Внутри имеются вершины двух типов: те, 
которые вершины для всех содержащих их $k$-угольников 
(пусть их $m$), и те которые строго 
внутри стороны какого-нибудь $k$-угольника (пусть их $l$).
 
 $$n(k-2)\pi=2\pi m+\pi l+(s-2)\pi$$ (счёт углов)
 $$
n(k-2)=2m+l+s-2\quad  (1)
$$
 
 Кроме того, 
$$nk\le 3m+2l+s\quad (2)$$ 
(количество точек, внутренних и на краю). Вычтем и получим:
 
 $$2n\le m+l+2>m+l\quad (3)$$
 
 Из (1) и (3) выводим $\frac{n(k-2)-s+2}{2}<2n$ (так как $m+l>m+\frac{l}{2}$,
 то есть $n(k-6)<s-2<s$).
 
 Пусть следующий слой состоит из $t$ $k$-угольников, $s'$~--- количество
 строк у нового (рассмотренного многоугольника. $s'>(k-6)(n+t)$, так как
 $kt>s+s'$ (очевидно, так как $kt$~--- число сторон), то есть
 $kt>(k-6)(n+t)+(k-6)n \to t>\frac{k-6}{3}n$, то есть в каждом
 дополнительном слое мнооугольников в $\frac{k}{3}$ раз больше, чем было
 в $s$-угольнике, значит, внутри круга радиуса $R$, начиная с некоторого~$R_0$,
 будет $>\left(\frac{k}{10}\right)^R$ многоугольников.
 
 \task{D10} Отразим полуплоскотсь на другую половину, получим $2k$ отмеченных
 многоугольников. Используя $D9$, получаем, что число примыкающих к ним
 $k$-угольников (первый слой), больше $\frac{k-6}{3}2l$, во втором слое
 $\left(\frac{k-6}{3}\right)^2 2l$ и так далее, $\dots$, в $i$-ом слое
 более $\left(\frac{k-6}{3}\right)^i2l$, учитывая, что для больших $k$
 $\frac{k-6}{3}>\frac{k}{10}$, получаем, что требуется.


%\end{eqnarray}


\end{document}
