Максимальное количество обгонов в эстафете

Сначала докажем, что произошло не более $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 обгонов.

Проиллюстрируем пример для случая команд, состоящих из двух участников (см. рисунок, первая команда — сплошная чёрная ломаная, вторая — пунктирная).