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 3 of 3: Inductive sink construction reaches every even vertex 2k
Previous stepNext step
For 1≤k≤n, set sinks {k+1,…,k+n}:source k−i ⟶ sink k+i+1(mod2n)\text{For }1\le k\le n,\text{ set sinks }\{k+1,\ldots,k+n\}:\quad\text{source }k-i\ \longrightarrow\ \text{sink }k+i+1\pmod{2n}
Detailed analysis

Fix k∈{1,…,n}k\in\{1,\ldots,n\} and orient chord i↔i+ni\leftrightarrow i+n towards i+ni+n for 1≤i≤k1\le i\le k and towards ii for k<i≤nk<i\le n, so the sinks are k+1,k+2,…,k+nk+1,k+2,\ldots,k+n. Launch nn presents simultaneously from the nn non-sink endpoints. We prove by induction on nn that the present from k−ik-i reaches k+i+1k+i+1 (modulo 2n2n) for i=0,1,…,n−1i=0,1,\ldots,n-1 along pairwise non-crossing paths: removing the chord k→k+nk\to k+n, the induction hypothesis routes k−ik-i to k+i+2k+i+2 for 1≤i≤n−11\le i\le n-1 along non-crossing paths that meet the chord k→k+nk\to k+n in increasing order of ii; reinserting the chord k→k+nk\to k+n diverts the present from kk onto the first path to k+1k+1 and shifts each subsequent path from k−ik-i onto the old segment leading to k+i+1k+i+1. Setting i=k−1i=k-1 sends Tony's present from 1=k−(k−1)1=k-(k-1) to k+(k−1)+1=2kk+(k-1)+1=2k. Varying k=1,…,nk=1,\ldots,n reaches all nn even vertices 2,4,…,2n2,4,\ldots,2n.