57-я Международная Математическая OлимпиадаГонконг, 2016 год

На плоскости расположено $n \geq 2$ отрезков так, что любые два из них пересекаются по внутренней точке, а никакие три из них не имеют общей точки. Иван выбирает один из концов каждого отрезка и сажает в него лягушку лицом к другому концу этого отрезка. Затем он $n - 1$ раз хлопает в ладоши. При каждом хлопке каждая из лягушек немедленно прыгает вперёд в следующую точку пересечения на её отрезке. Лягушки никогда не меняют направления своих прыжков. Иван хочет изначально рассадить лягушек так, чтобы никакие две из них никогда не оказались в одной точке пересечения одновременно.
(a) Докажите, что Иван всегда может добиться желаемого, если $n$ нечётно.
(b) Докажите, что Иван никогда не сможет достичь желаемого, если $n$ чётно.

Комментарий/решение

Представьте, что вы взяли круг ω большего размера, охватывающий все n точек пересечения. Обозначим через P1, P2, . , P2n — порядок точек на ω по часовой стрелке; мы представляем, как размещаем лягушек на

Вместо этого Пи. Обратите внимание, что для того, чтобы каждая пара сегментов встретилась, каждый сегмент прямой должен иметь форму PiPi+n.

Затем:

(а) Поместите лягушек на P1, P3, . . . , P2n−1. Простое рассуждение о четности показывает, что это работает.

(б) Заметьте, что мы не можем разместить лягушки на последовательных точках числа Пи, поэтому n лягушек необходимо разместить в чередующихся точках. Но так как нам тоже не положено расставлять лягушек в диаметрально противоположных точках, то при четном n сразу получаем противоречие.

Замечание:до этого легко догадаться, если вы просто проделаете несколько небольших случаев и заметите, что пары «точек нарушения» просто образуют большой цикл вокруг