Задача
№ 14253
Оценка + пример (экстремальные комбинаторные задачи)
Ур. 6
Всероссийская олимпиада школьников по математике, 9 класс, муниципальный этап 2021/22 уч. г. (Москва), задача 8
На плоскости отмечено 36 точек, никакие три из которых не лежат на одной прямой. Некоторые пары отмеченных точек соединены отрезком так, что из каждой отмеченной точки выходит не более 3 отрезков.
Какое наибольшее количество различных замкнутых 4-звенных ломаных может получиться?
Вершинами ломаной могут быть только отмеченные точки, а звеньями — только проведённые отрезки. Неважно, где у ломаной начало и как она ориентирована: например, если для некоторых 4 отмеченных точек $A$, $B$, $C$, $D$ проведены отрезки $AB$, $BC$, $CD$, $DA$, то $ABCD$, $BCDA$, $CDAB$, $DABC$, $ADCB$, $BADC$, $CBAD$, $DCBA$ — это одна и та же ломаная.
Какое наибольшее количество различных замкнутых 4-звенных ломаных может получиться?
Вершинами ломаной могут быть только отмеченные точки, а звеньями — только проведённые отрезки. Неважно, где у ломаной начало и как она ориентирована: например, если для некоторых 4 отмеченных точек $A$, $B$, $C$, $D$ проведены отрезки $AB$, $BC$, $CD$, $DA$, то $ABCD$, $BCDA$, $CDAB$, $DABC$, $ADCB$, $BADC$, $CBAD$, $DCBA$ — это одна и та же ломаная.
Ответ:
Решение: