Problem 5

There are

n

line segments on the plane, no three intersecting at a point, and each pair intersecting once in their respective interiors. Tony and his

2n-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

n

of his

2n-1

friends.

Step 1 of 3: Circle-chord model and opposite-vertex pairing

Previous step Next step

\text{Vertices }1,\ldots,2n\text{ on a circle (Tony at }1\text{)};\quad\text{each chord connects }k\text{ and }k+n\pmod{2n}

Detailed analysis

Enclose all $\binom{n}{2}$ interior intersections inside a large circle, extend the $n$ segments to chords of this circle, and number the $2n$ chord endpoints $1,2,\ldots,2n$ anticlockwise starting with Tony at $1$ . Since every two chords intersect inside the circle, each chord has $n-1$ endpoints on either side, so it connects $k$ to $k+n$ for some $1\le k\le n$ .