ВсОШ 2022, 9 класс, задача 8
( баллов) На плоскости отмечено точек, никакие три из которых не лежат на одной прямой. Некоторые пары отмеченных точек соединены отрезком так, что из каждой отмеченной точки выходит не более отрезков.
Какое наибольшее количество различных замкнутых -звенных ломаных может получиться?
Вершинами ломаной могут быть только отмеченные точки, а звеньями — только проведённые отрезки. Неважно, где у ломаной начало и как она ориентирована: например, если для некоторых отмеченных точек , , , проведены отрезки , , , , то , , , , , , , — это одна и та же ломаная.
Ответ
Ответ: .
Решение. Для начала докажем, что ломаных не больше .
Рассмотрим конструкцию «галочка», состоящую из трёх точек , и , а также двух отрезков и (при этом отрезок может как присутствовать, так и не присутствовать; точку будем называть вершиной галочки). Так как из и выходит ещё не более чем по два отрезка, то каждая галочка может содержаться не более, чем в двух -звенных ломаных (рис. a). При этом точка является вершиной не более чем трёх галочек, поэтому она находится не более чем в шести -звенных ломаных.
Теперь оценим количество ломаных. Всего точек , каждая находится не более чем в ломаных, при этом в каждой ломаной участвуют ровно точки. Таким образом, ломаных не больше чем .
Теперь докажем, что ломаных могло быть ровно .
Опишем конструкцию, состоящую из точек: , , , , , (рис. b). Между ними проведём отрезки так, чтобы для всех точка была соединена с точкой (таким образом, из каждой точки выходит ровно отрезка). Тогда любая пара вершин , вместе с любой парой вершин , будет образовывать -звенную ломаную. Таким образом, ломаных будет ровно . Для построения примера, требующегося в задаче, достаточно рассмотреть таких конструкций, все точки которых различны.
Верное решение.