Решение задачи MM150 XV тура Математического марафона

главная страница сайта Приглашение в мир математики
======= 150 ========

ММ150 (12 баллов)

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

====================

Решение

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

Расставим черные бусины в углы многоугольника, которые меньше развернутого, и белые - в углы больше развернутого.
Конфигурация черных и белых бусин однозначно определяет цвет сторон. В обратную сторону однозначность нарушается, только если все стороны зеленые. Но возникающие при этом две две конфигурации переводятся друг в друга поворотом.
Таким образом задача свелась к подсчету числа ожерелий из бусин двух цветов. При этом черных бусин не меньше трех, так как в многоугольнике не меньше трех углов, меньших развернутого. (Для доказательства достаточно рассмотреть выпуклую оболочку исходного многоугольника.)
С другой стороны, любая конфигурация, в которой не менее трех черных бусин, очевидно, возможна. (Достаточно взять правильный 20-угольник и вдавить внутрь вершины, соответствующие белым бусинам.)

Подсчитаем количество черно-белых ожерелий без учета ограничения, что черных бусин не менее трех.
Воспользуемся леммой Бернсайда. В качестве группы преобразований $G$ выступает группа диэдра, состоящая из 20-и симметрий и 20-и поворотов (включая тождественный).
Если $g \in G$ - симметрия, ось которой проходит через две бусины, то для $g$ имеется $2^{11}$ неподвижных конфигураций. Если же ось симметрии не проходит через бусины, для $g$ имеется $2^{10}$ неподвижных конфигураций. Значит, вклад симметрий $10\left(2^{11}+2^{10}\right)$.
Для поворотов имеем сумму $$\frac1{40}\sum_{d|20}\varphi(d)2^{\frac{20}d}.$$ Итого получаем $$\frac1{40}\left(10\left(2^{11}+2^{10}\right)+2^{20}+2^{10}+2\cdot2^5+4\cdot2^4+4\cdot2^2+8\cdot2\right)=27012.$$

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

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

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

С помощью леммы Бернсайнда можно вывести и явную формулу для подсчета ожерелий, в которых число бусин каждого цвета фиксировано. Например, число черно-белых ожерелий из $n$ бусин, среди которых и $m$ черных, подсчитывается по формуле $$\frac12\left(\frac1n \sum_{d|(n,m)}\varphi(d)C^{m/d}_{n/d}+C^{\lfloor m/2\rfloor}_{\lfloor (n-m)/2\rfloor+\lfloor m/2\rfloor}\right).$$
Вывод этой формулы можно посмотреть, например, здесь.
При $n=20$, суммируя по всем $m \ge3$, вновь получим 27000.

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

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


Награды

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

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

Разбор задачи ММ150 подготовил Владимир Лецко

-- 01 ноя 2011, 19:36 --

Итоговое положение участников в тематическом конкурсе
XV тура Математического марафона

Задайте вопрос на блоге о математике