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 : $\bullet$ If it is on a line segment, it moves towards the sink. $\bullet$ 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.
Problem
Source:
Tags: combinatorics, APMO, APMO 2023
06.07.2023 04:51
wow, what a unique idea
06.07.2023 06:42
Is Geoff one of Tony's friends?
06.07.2023 06:52
lines are cool
14.07.2023 11:51
say $f(l)=1$ if the present is on line $l$ or at the left side of us $l$ when we stand on $l$ facing the sink else $f(l)=0$ we can proof that $\sum f(l)$ is a CONSTANT. thus we only need two things: present stops at somewhere and only the endpiont i like MIGHT be the place where the present stops
14.07.2023 15:57
reminds of the famous windmill problem 2011 IMO P2
14.07.2023 16:53
Color the regions formed by lines black and white where any two adjacent regions have different colors. Draw clockwise arrows around each white region and counterclockwise arrows around each black region. Then, the present must follow arrows in the same direction, so since there are exactly $n$ arrows in each direction, it is possible to send the present to at most $n$ friends. Now, consider rotating the entire diagram, then letting the sink be the endpoint with larger $x$-coordinate. Since there are always the same amount of lines above the present, this means that a suitable rotation allows the present to reach any of the $n$ possible friends.
04.03.2024 17:59
something something bijective process Extend the segments to lines, then consider a large circle $\omega$ containing every intersection point. Now cut off the lines at their intersection points with $\omega$ and move everyone to the intersection points in the obvious way; clearly this doesn't change anything. Refer to the non-sink endpoint of each segment as a source. It is clear that, starting from any source, our present cannot end up stuck in a cycle, since by inspection our present could never have entered this cycle to begin with. Now suppose we place a present at every source and move the presents as described, tracking each present's path until it eventually ends up at a sink. It is then clear that these paths never intersect. Note that this implies that two presents from different sources must end up at different sinks. Let Tony stand at point $T$. I claim that Tony cannot send a present to any endpoint $F$ such that chord $\overline{TF}$ cuts the circumference of $\omega$ into two arcs each containing an odd number of endpoints (including neither $T$ nor $F$). Indeed, suppose that this was possible for some fixed choice of sources/sinks; evidently $T$ is a source and $F$ is a sink. Then because each has an odd number of points, one of the two arcs produced by the cut must have strictly more sources than sinks, so there exists a source where a present starting from it must end up in a sink in the other arc. But then it clearly must cross the path of the present moving from $T$ to $F$. Now it suffices to show that Tony can always send a present to an endpoint $F$ if chord $\overline{TF}$ cuts the circumference of $\omega$ into two regions each containing an even number of endpoints. Fix a choice of $F$. There evidently exists some chord $\overline{AB}$ of $\omega$ (not passing through any endpoint) that cuts the circumference of $\omega$ into two arcs, each containing an even number of endpoints, such that if we label the endpoints $P_1,\ldots,P_n,Q_n,\ldots,Q_1$ in counterclockwise order starting from $A$, then we have $T=P_k$ and $F=Q_k$ for some $k$. Suppose there exist $i_1,i_2$ such that $\overline{P_{i_1}P_{i_2}}$ is present as a segment. Then because there are not enough remaining points on the "$P$ arc" of $\overline{AB}$ to pair with every point on the "$Q$ arc", there must exist $j_1,j_2$ such that $\overline{Q_{j_1}Q_{j_2}}$ is also present as a segment. But then these segments don't intersect, contradicting the definition of $\omega$. Hence every $P_i$ is connected to some (unique) $Q_j$. We may now select every $P_i$ as a source and every $Q_i$ as a sink. If we again place a present at each $P_i$, the presents eventually end up at all of the $Q_j$. But because present paths do not intersect, the present starting at $P_i$ must end up at $Q_i$ for all $i$, since the existence of some $i_1>j_1$ (resp. $i_1<j_1$) such that the present at $P_{i_1}$ ends up at $Q_{j_1}$ implies (by Pigeonhole) the existence of some $i_2<i_1$ and $j_2>j_1$ (resp. $i_2>i_1$ and $j_2<j_1$) such that the present at $P_{i_2}$ ends up at $Q_{j_2}$, but then their paths intersect: contradiction. Thus the present starting at $T=P_k$ ends at $F=Q_k$, as desired. $\blacksquare$