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