APMO

Draw a circle that encloses all the intersection points between line segments and extend all line segments until they meet the circle, and then move Tony and all his friends to the circle. Number the intersection points with the circle from 1 to $2n$ anticlockwise, starting from Tony (Tony has number 1). We will prove that the friends eligible to receive presents are the ones on even-numbered intersection points.

First part: at most $n$ friends can receive a present.

The solution relies on a well-known result: the $n$ lines determine regions inside the circle; then it is possible to paint the regions with two colors such that no regions with a common (line) boundary have the same color. The proof is an induction on $n$ : the fact immediately holds for $n=0$, and the induction step consists on taking away one line $\ell$, painting the regions obtained with $n-1$ lines, drawing $\ell$ again and flipping all colors on exactly one half plane determined by $\ell$.

Now consider the line starting on point 1. Color the regions in red and blue such that neighboring regions have different colors, and such that the two regions that have point 1 as a vertex are red on the right and blue on the left, from Tony's point of view. Finally, assign to each red region the clockwise direction and to each blue region the anticlockwise direction. Because of the coloring, every boundary will have two directions assigned, but the directions are the same since every boundary divides regions of different colors. Then the present will follow the directions assigned to the regions: it certainly does for both regions in the beginning, and when the present reaches an intersection it will keep bordering one of the two regions it was dividing. To finish this part of the problem, consider the regions that share a boundary with the circle. The directions alternate between outcoming and incoming, starting from 1 (outcoming), so all even-numbered vertices are directed as incoming and are the only ones able to receive presents.

Second part: all even-numbered vertices can receive a present.

First notice that, since every two chords intersect, every chord separates the endpoints of each of the other $n-1$ chords. Therefore, there are $n-1$ vertices on each side of every chord, and each chord connects vertices $k$ and $k+n,1\le k\le n$.

We prove a stronger result by induction in $n$ : let $k$ be an integer, $1\le k\le n$. Direct each chord from $i$ to $i+n$ if $1\le i\le k$ and from $i+n$ to $i$ otherwise; in other words, the sinks are $k+1,k+2,\dots ,k+n$. Now suppose that each chord sends a present, starting from the vertex opposite to each sink, and all presents move with the same rules. Then $k-i$ sends a present to $k+i+1,i=0,1,\dots ,n-1$ (indices taken modulo $2n$ ). In particular, for $i=k-1$, Tony, in vertex 1, send a present to vertex $2k$. Also, the $n$ paths the presents make do not cross (but they may touch.) More formally, for all $i,1\le i\le n$, if one path takes a present from $k-i$ to $k+i+1$, separating the circle into two regions, all paths taking a present from $k-j$ to $k+j+1,j<i$, are completely contained in one region, and all paths taking a present from $k-j$ to $k+j+1,j>i$, are completely contained in the other region. For instance, possible $\{{\}}^{\{}1\}$ paths for $k=3$ and $n=5$ follow:



The result is true for $n=1$. Let $n>1$ and assume the result is true for less chords. Consider the chord that takes $k$ to $k+n$ and remove it. Apply the induction hypothesis to the remaining $n-1$ lines: after relabeling, presents would go from $k-i$ to $k+i+2,1\le i\le n-1$ if the chord were not there.

Reintroduce the chord that takes $k$ to $k+n$. From the induction hypothesis, the chord intersects the paths of the presents in the following order: the $i$-th path the chord intersects is the the one that takes $k-i$ to $k+i,i=1,2,\dots ,n-1$.



Paths without chord $k\to k+n$



Corrected paths with chord $k\to k+n$

Then the presents cover the following new paths: the present from $k$ will leave its chord and take the path towards $k+1$; then, for $i=1,2,\dots ,n-1$, the present from $k-i$ will meet the chord from $k$ to $k+n$, move towards the intersection with the path towards $k+i+1$ and go to $k+i+1$, as desired. Notice that the paths still do not cross. The induction (and the solution) is now complete.

---

Alternative solution.

First part: at most $n$ friends can receive a present.

Similarly to the first solution, consider a circle that encompasses all line segments, extend the lines, and use the endpoints of the chords instead of the line segments, and prove that each chord connects vertices $k$ and $k+n$. We also consider, even in the first part, $n$ presents leaving from $n$ outcoming vertices.

First we prove that a present always goes to a sink. If it does not, then it loops; let it first enter the loop at point $P$ after turning from chord $a$ to chord $b$. Therefore after it loops once, it must turn to chord $b$ at $P$. But $P$ is the intersection of $a$ and $b$, so the present should turn from chord $a$ to chord $b$, which can only be done in one way - the same way it came in first. This means that some part of chord $a$ before the present enters the loop at $P$ is part of the loop, which contradicts the fact that $P$ is the first point in the loop. So no present enters a loop, and every present goes to a sink.



There are no loops



No two paths cross

The present paths also do not cross: in fact, every time two paths share a point $P$, intersection of chords $a$ and $b$, one path comes from $a$ to $b$ and the other path comes from $b$ to $a$, and they touch at $P$. This implies the following sequence of facts: - Every path divides the circle into two regions with paths connecting vertices within each region. - All $n$ presents will be delivered to $n$ different persons; that is, all sinks receive a present. This implies that every vertex is an endpoint of a path. - The number of chord endpoints inside each region is even, because they are connected within their own region.

Now consider the path starting at vertex 1, with Tony. It divides the circle into two regions with an even number of vertices in their interior. Then there is an even number of vertices between Tony and the recipient of his present, that is, their vertex is an even numbered one.

Second part: all even-numbered vertices can receive a present.

The construction is the same as the in the previous solution: direct each chord from $i$ to $i+n$ if $1\le i\le k$ and from $i+n$ to $i$ otherwise; in other words, the sinks are $k+1,k+2,\dots ,k+n$. Then, since the paths do not cross, $k$ will send a present to $k+1,k-1$ will send a present to $k+2$, and so on, until 1 sends a present to $(k+1)+(k-1)=2k$.