Процессы и алгоритмы

Оценка. Рассмотрим шаг, на котором Василий помечает некоторый отрезок Перед этим шагом из каждой из точек и выходит максимум по отрезка, и они содержат максимум различных пометки. Значит, Василий точно сможет пометить этот отрезок числом, не превосходящим Итак,

Если чётно, эту оценку можно уточнить следующим образом. Назовём маленьким отрезок, помеченный единицей. Докажем, что в конце процесса из каждой точки будет выходить маленький отрезок; предположим противное. Точки, из которых выходят маленькие отрезки, разбиваются на пары точек, соединённых таким отрезком. Значит, есть хотя бы две точки и из которых не выходит маленьких отрезков. Выходит, что когда Василий проводил отрезок он должен был пометить его единицей — противоречие.

Значит, если отрезок не будет маленьким, то в конце процесса среди отрезков, выходящих из и кроме будут два маленьких отрезка. Значит, на этих отрезках будет максимум различных пометок. Следовательно, когда Василий будет проводить отрезок он сможет пометить его числом, не превосходящим и

Пример. Осталось доказать, что Василий может достичь указанных значений

______________________________________________________________________________________________________________________________________________________

Лемма. Если количество точек чётно и равно то Василий может пометить все отрезки между этими точками, использовать лишь числа от до При этом из каждой точки выходит ровно по одному отрезку с каждой пометкой.

Доказательство. Утверждение леммы не зависит от конкретного расположения точек, так что можно считать, что точек расположены в вершинах правильного -угольника, а оставшаяся точка — в его центре

Тогда все отрезки между этими точками можно разбить на множеств так, чтобы отрезки одного множества не имели общих концов. Например, в множество можно включить отрезок и все отрезки, соединяющие пары вершин -угольника и перпендикулярные Из каждой точки выходит по отрезку каждого из множеств.

Теперь Василий может сначала пометить все отрезки множества числом 1, затем все отрезки второго множества числом 2, и т. д.

_________________________________________________________________________________________________________________________________________________________________________________

Вернёмся к решению. Пусть нечётно, и пусть — отмеченная точка. Пусть Василий сначала пометит все отрезки между точками, отличными от числами от 1 до согласно лемме. Затем он проведёт отрезок из каждый отрезок ему придётся помечать числом, большим ибо из уже выходят отрезки, помеченные всеми меньшими числами. Кроме того, все эти отрезок будут помечены разными числами, ибо у них есть общий конец. Следовательно, они будут помечены числами

то есть Василий получит пометку

Пусть теперь чётно. Выберем две отмеченных точки и пусть

— остальные отмеченные точки. Пусть Василий сначала пометит все отрезки между точками числами от 1 до согласно лемме, а также пометит отрезок числом 1. Затем он последовательно проводит отрезки

поскольку в вершины уже входят отрезки с пометками от 1 до новые отрезки будут помечены числами

соответственно. Далее Василий проводит отрезки

аналогично, он пометит их числами

соответственно.

Теперь в вершины и уже входят отрезки со всеми пометками от до а в вершину — со всеми пометками от 1 до Значит, когда Василий проводит отрезки и первый будет помечен числом а второй — числом (ибо имеет общий конец с предыдущим). Значит, Василий добился появления числа