2. In the relay race Moscow - Petushki, two teams of 20 people each participated. Each team divided the distance into 20 not necessarily equal segments and distributed them among the participants so that each ran exactly one segment (the speed of each participant is constant, but the speeds of different participants may vary). The first participants of both teams started simultaneously, and the baton handover happens instantaneously. What is the maximum number of overtakes that could occur in such a race? Overtaking at the segment boundaries is not counted as an overtake.

(2023-96, E. Neustroeva)
Answer: 38 overtakes.

Solution. First, let's prove that no more than 38 overtakes occurred. Note that between the start and the first overtake, and between two consecutive overtakes, at least one of the teams must have changed the runner. There were 19 changes of runners in each team, meaning a total of 38 changes, so there could not have been more than 38 overtakes.

Let's prove that 38 overtakes were possible. We will illustrate the movement trajectories of the teams on a graph with the horizontal axis representing time and the vertical axis representing the segments, directed upwards and to the right. The lower-left end of each broken line coincides with the origin, and the upper-right ends of the broken lines have the same vertical coordinate. In this situation, an overtake is a point of intersection of the broken lines that is not a vertex.

So, let's provide an example. First, draw a broken line consisting of 40 consecutive sides of a regular 160-gon, such that the last side is horizontal. In other words, the first segment of the broken line starts from the point with coordinates \((0,0)\) and is rotated at an angle of \(9/4^{\circ}\), and each subsequent segment is rotated by \(9/4^{\circ}\) clockwise compared to the previous one. Thus, the last segment will be horizontal, i.e., rotated by \(40 \cdot 9/4^{\circ} = 90^{\circ}\) relative to the vertical axis. Connect the vertices of the auxiliary broken line with numbers \(1, 2, 4, 6, \ldots, 50\) sequentially with line segments; this will be the trajectory of the first team. The trajectory of the second team will be a broken line connecting the vertices with numbers \(1, 3, 5, \ldots, 51\). The segments \((i, i+2)\) and \((i+1, i+3)\) for \(i=1, 2, \ldots, 38\) will intersect, and their points of intersection will be the 38 overtakes we are looking for.

Let's illustrate the example for the case of teams consisting of two participants.

![](https://cdn.mathpix.com/cropped/2024_05_06_fde2078dee7bae03239bg-01.jpg?height=52&width=1674&top_left_y=2187&top_left_x=154)

![](https://cdn.mathpix.com/cropped/2024_05_06_fde2078dee7bae03239bg-02.jpg?height=763&width=1019&top_left_y=258&top_left_x=473)

Fig. 1: to the solution of problem 2