ВсОШ 2022, 10 класс, задача 4
( баллов) Дано натуральное число . На плоскости отмечены точек, никакие три из которых не лежат на одной прямой. Василий проводит по одному все отрезки, соединяющие пары отмеченных точек. На каждом шаге, проводя очередной отрезок , Василий помечает его наименьшим натуральным числом, которым ещё не помечен ни один отрезок, имеющий с общий конец. Для какого наибольшего Василий может действовать так, чтобы пометить какой-то отрезок числом ? (А. Глебов, Д. Храмцов)
Ответ
Ответ.
при нечётном , и при чётном .
Решение.
Оценка.
Рассмотрим шаг, на котором Василий помечает некоторый отрезок . Перед этим шагом из каждой из точек и выходит максимум по отрезка, и они содержат максимум различных пометки. Значит, Василий точно сможет пометить этот отрезок числом, не превосходящим . Итак, . Если чётно, эту оценку можно уточнить следующим образом. Назовём маленьким отрезок, помеченный единицей. Докажем, что в конце процесса из каждой точки будет выходить маленький отрезок; предположим противное. Точки, из которых выходят маленькие отрезки, разбиваются на пары точек, соединённых таким отрезком. Значит, есть хотя бы две точки и , из которых не выходит маленьких отрезков. Выходит, что когда Василий проводил отрезок , он должен был пометить его единицей — противоречие. Значит, если отрезок не будет маленьким, то в конце процесса среди отрезков, выходящих из и , кроме , будут два маленьких отрезка. Значит, на этих отрезках будет максимум различных пометок. Следовательно, когда Василий будет проводить отрезок , он сможет пометить его числом, не превосходящим , и .
Пример.
Осталось доказать, что Василий может достичь указанных значений .
Лемма.
Если количество точек чётно и равно , то Василий может пометить все отрезки между этими точками, использовав лишь числа от до . При этом из каждой точки будут выходить отрезки, помеченные всеми этими числами.
Доказательство.
Утверждение леммы не зависит от конкретного расположения точек, так что можно считать, что точек расположены в вершинах правильного ()-угольника, а оставшаяся точка — в его центре . Тогда все отрезки между этими точками можно разбить на множеств так, чтобы отрезки одного множества не имели общих концов. Например, в множество можно включить отрезок и все отрезки, соединяющие пары вершин ()-угольника и перпендикулярные . Из каждой точки выходит по отрезку каждого из множеств. Теперь Василий может сначала пометить все отрезки множества числом , затем все отрезки второго множества числом , и т. д. Вернёмся к решению. Пусть нечётно, и пусть — отмеченная точка. Пусть Василий сначала пометит все отрезки между точками, отличными от , числами от до согласно лемме. Затем он проведёт все отрезок из ; каждый отрезок ему придётся помечать числом, большим , ибо из уже выходят отрезки, помеченные всеми меньшими числами. Кроме того, все эти отрезков будут помечены разными числами, ибо у них есть общий конец. Следовательно, они будут помечены числами , ... , , то есть Василий получит пометку . Пусть теперь чётно. Выберем две отмеченных точки и ; пусть — остальные отмеченные точки. Пусть Василий сначала пометит все отрезки между точками числами от до согласно лемме, а также пометит отрезок числом . Затем он последовательно проводит отрезки ; поскольку в вершины уже входят отрезки с пометками от до , новые отрезки будут помечены числами , ... , соответственно. Далее Василий проводит отрезки ; аналогично, он пометит их числами , ... , соответственно. Теперь в вершины и уже входят отрезки со всеми пометками от до , а в вершину — со всеми пометками от до . Значит, когда Василий проводит отрезки и , первый будет помечен числом , а второй — числом (ибо имеет общий конец с предыдущим). Значит, Василий добился появления числа .