|
|
 |
Условие
В эстафетном забеге Москва—Петушки участвовали две команды по $20$ человек. Каждая из команд по-своему разделила дистанцию на $20$ не обязательно равных отрезков и распределила их между участниками так, чтобы каждый бежал ровно один отрезок (скорость каждого участника постоянна, но скорости разных участников могут быть различны). Первые участники обеих команд стартовали одновременно, а передача эстафеты происходит мгновенно. Какое максимальное количество обгонов могло быть в таком забеге? Опережение на границе этапов обгоном не считается.Решение
Сначала докажем, что произошло не более $38$ обгонов. Заметим, что между стартом и первым обгоном и между двумя последовательными обгонами хотя бы в одной из команд должен поменяться бегущий. Смен бегунов было по $19$ в каждой команде, то есть всего $38$, а значит, и обгонов было не более $38$.Докажем, что $38$ обгонов могло быть. Изобразим траектории движения команд на графике с горизонтальной осью, соответствующей времени, и вертикальной осью, соответствующей пройденной дистанции. Тогда обе траектории являются $20$-звенными ломаными со звеньями, направленными вверх-вправо. Левый нижний конец каждой ломаной совпадает с началом координат, а правые верхние концы ломаных имеют одинаковую ординату. В такой ситуации обгон — точка пересечения ломаных, не являющаяся вершиной.
Итак, приведём пример. Для начала нарисуем ломаную, состоящую из 40 последовательных сторон правильного 160-угольника, так чтобы последняя сторона была горизонтальна. Другими словами, первое звено ломаной выходит из точки с координатами $(0,0)$ под углом в $9/4^{\circ}$ к вертикали, а каждое следующее повёрнуто на $9/4^{\circ}$ по часовой стрелке по сравнению с предыдущим. Таким образом, последнее звено будет повёрнуто горизонтально, то есть на $40 \cdot 9/4^{\circ} = 90^{\circ}$ относительно вертикальной оси. Занумеруем последовательно все вершины от 1 до 41 и соединим вершины с номерами $1$, $2$, $4$, $6$, ..., $40$, это будет траектория первой команды. Траекторией второй команды будет ломаная, соединяющая вершины с номерами $1$, $3$, $5$, ..., $41$. Пересекаться будут отрезки $(i, i+2)$ и $(i+1, i+3)$ для $i = 1, 2, \ldots, 38$, их точки пересечения — искомые 38 обгонов.
Проиллюстрируем пример для случая команд, состоящих из двух участников (см. рисунок, первая команда — сплошная чёрная ломаная, вторая — пунктирная).
