MathLabs

Problem 5

There are nn line segments on the plane, no three intersecting at a point, and each pair intersecting once in their respective interiors. Tony and his 2n−12n-1 friends each stand at a distinct endpoint of a line segment. Tony wishes to send Christmas presents to each of his friends as follows: First, he chooses an endpoint of each segment as a "sink". Then he places the present at the endpoint of the segment he is at. The present moves as follows: if it is on a line segment, it moves towards the sink; when it reaches an intersection of two segments, it changes the line segment it travels on and starts moving towards the new sink. If the present reaches an endpoint, the friend on that endpoint can receive their present. Prove that Tony can send presents to exactly nn of his 2n−12n-1 friends.
Step 2 of 3: At most the n even vertices can receive a present
2-color regions red (clockwise) / blue (anticlockwise) ⟹ boundary directions alternate: odd outgoing, even incoming\text{2-color regions red (clockwise) / blue (anticlockwise)}\ \Longrightarrow\ \text{boundary directions alternate: odd outgoing, even incoming}
Detailed analysis

Two-color the regions cut out by the nn chords inside the circle red and blue so that adjacent regions have different colors, with the two regions incident to vertex 11 colored red on the right and blue on the left viewed from 11. Orient the boundary of every red region clockwise and every blue region anticlockwise; every chord segment separating a red and a blue region receives the same orientation from both sides. A present starting at 11 moves along its chord in the direction consistent with the two adjacent regions, and at each intersection it turns onto the crossing chord while continuing to border one of those two regions, so it always follows the region orientation. Around the outer circle the region colors alternate, so the chord orientations at vertices 1,2,…,2n1,2,\ldots,2n alternate between outgoing at odd vertices and incoming at even vertices. Hence a present from 11 can only exit at the nn even-numbered vertices 2,4,…,2n2,4,\ldots,2n.