Задача
№ 14295
Оценка + пример (экстремальные комбинаторные задачи)
Ур. 7
Всероссийская олимпиада школьников по математике, 11 класс, заключительный этап, 2022, задача 4; также: ВОШ 10 кл. ЗЭ 2022 №4
Дано натуральное число $n\gt 4$. На плоскости отмечены $n$ точек, никакие три из которых не лежат на одной прямой. Василий проводит по одному все отрезки, соединяющие пары отмеченных точек. На каждом шаге, проводя очередной отрезок $S$, Василий помечает его наименьшим натуральным числом, которым ещё не помечен ни один отрезок, имеющий с $S$ общий конец. Для какого наибольшего $k$ Василий может действовать так, чтобы пометить какой-то отрезок числом $k$?
Ответ:
Решение: