===== MM150 =====

**Конукрсная задача ММ150 (КГ15)** (12 баллов)

Каждому n-угольнику поставим в соответствие ожерелье из n бусин белого, зеленого и красного цветов следующим образом: свободой стороне соответствует белая бусина; полусвободной - зеленая; зажатой - красная.
Два n-угольника назовем эквивалентными, если им соответствуют одинаковые ожерелья (ожерелье не меняется при поворотах и переворачивании). На сколько классов эквивалентности разобьются 20-угольники?

**Решение**

Еще раз приведу решение Андрея Халявина.

Расставим черные бусины в углы многоугольника, которые меньше развернутого, и белые - в углы больше развернутого.
Конфигурация черных и белых бусин однозначно определяет цвет сторон. В обратную сторону однозначность нарушается, 
только если все стороны зеленые. Но возникающие при этом две две конфигурации переводятся друг в друга поворотом.
Таким образом задача свелась к подсчету числа ожерелий из бусин двух цветов. При этом черных бусин не меньше трех,
так как в многоугольнике не меньше трех углов, меньших развернутого. (Для доказательства достаточно рассмотреть 
выпуклую оболочку исходного многоугольника.)
С другой стороны, любая конфигурация, в которой не менее трех черных бусин, очевидно, возможна. 
(Достаточно взять правильный 20-угольник и вдавить внутрь вершины, соответствующие белым бусинам.)
 
Подсчитаем количество черно-белых ожерелий без учета ограничения, что черных бусин не менее трех.
Воспользуемся леммой Бернсайда. В качестве группы преобразований G выступает группа диэдра, состоящая из 20-и симметрий 
и 20-и поворотов (включая тождественный).
Если g из G - симметрия, ось которой проходит через две бусины, то для g имеется 2<sup>11</sup> неподвижных конфигураций. 
Если же ось симметрии не проходит через бусины, для g имеется 2<sup>10</sup> неподвижных конфигураций. 
Значит, вклад симметрий 10(2<sup>11</sup>+2<sup>10</sup>).
Для поворотов имеем сумму <m>1/{40}sum{d|20}{}phi(d)2^{{20}/d}</m>. 
Итого получаем (10(2<sup>11</sup>+2<sup>10</sup>)+2<sup>20</sup>+2<sup>10</sup>+2*2<sup>5</sup>+4*2<sup>4</sup>+4*2<sup>2</sup>+8*2)/40=27012.

Очевидно, что существует ровно одно ожерелье из белых бусин, одно ожерелье с одной черной бусиной и 10 ожерелий 
с двумя черными бусинами. Поэтому окончательно получаем 27012-1-1-10=27000 классов 20-угольников. 

 
**Обсуждение**

Задача о подсчете числа ожерелий широко известна. Наиболее подробное и доступное изложение (среди известных 
мне) можно найти в книге Дж. Андерсона "Дискретная математика и комбинаторика".

Разумеется, вместо 20-угольников можно было рассматривать произвольные n-угольники. Число 20 привлекло меня 
красотой ответа, являющегося в этом случае круглым числом и, к тому же, полным кубом!

С помощью леммы Бернсайнда можно вывести и явную формулу для подсчета ожерелий, в которых число бусин 
каждого цвета фиксировано. Например, число черно-белых ожерелий из n бусин, среди которых и m черных, 
подсчитывается по формуле <m>1/2(1/n sum{d|(n,m)}{}phi(d)(matrix{2}{1}{n/d m/d})+(matrix{2}{1}{{[(n-m)/2]+[m/2]} {[m/2]}}))</m>.
Вывод этой формулы можно посмотреть, например, здесь: http://www.omsu.omskreg.ru/vestnik/articles/y1998-i2/a021/article.html
При n = 20, суммируя по всем m ≥ 3, вновь получим 27000.  

Интересно, что если не различать полусвободные и зажатые стороны, задача станет сложнее. 
Пусть свободным сторонам соответствуют белые бусины, а прочим - красные. Если сторона не является свободной, 
то хотя бы одна из соседних с ней сторон тоже не является свободной. Поэтому красная бусина не может быть окружена белыми. Таким образом, при n > 5 интересующее нас число классов равно количеству ожерелий, 
которые можно составить из n белых и красных бусин, при условии, что никакая красная бусина не окружена белыми. 
Я посчитал количество классов для всех n ≤ 18 (например, при n=18 получается 799 классов), но общей формулы мне вывести не удалось.

В заключение еще об одной классификации, для которой мне не удалось вывести общую формулу для подсчета числа классов.
Будем считать эквивалентными n-угольники, у которых поровну как внутренних, так и внешних диагоналей. 
Можно показать, что число классов не превосходит (n<sup>4</sup>-10n<sup>3</sup>+39n<sup>2</sup>-70n+56)/8. Но, начиная с n=6, эта оценка завышена.


**Награды**

За правильное решение задачи ММ150 Алексей Волошин, Анатолий Казмерчук и Андрей Халявин получают по 12 призовых баллов. Сергей Половинкин получает 11, Виктор Филимоненков - 9 призовых баллов. 

**Эстетическая оценка - 4.2 балла**

//Разбор задачи ММ150 подготовил Владимир Лецко//
----
[[mm_150_appendix|Приложение]]