Problem 6

There are

n\ge2

line segments in the plane such that every two segments cross, and no three segments meet at a point. Geoff has to choose an endpoint of each segment and place a frog on it, facing the other endpoint. Then he will clap his hands

n-1

times; each time he claps, every frog immediately jumps forward to the next intersection point on its segment (frogs never change the direction of their jumps). Geoff wishes to place the frogs so that no two of them ever occupy the same intersection point at the same time. (a) Prove that Geoff can always fulfil his wish if

n

is odd. (b) Prove that Geoff can never fulfil his wish if

n

is even.

Step 1 of 4: Encircle the configuration and relabel

Previous step Next step

In plain words

Projecting each segment's endpoints outward onto a large surrounding circle keeps track of the cyclic order without changing which segments cross which.

\omega\supset\{\text{all }\tbinom n2\text{ intersection points}\},\qquad P_1,\dots,P_{2n}\ \text{in clockwise order}

Detailed analysis

Take a circle $\omega$ large enough to contain all $\binom n2$ intersection points of the $n$ segments in its interior, and extend each segment outward in both directions until it meets $\omega$ ; relabel the resulting $2n$ points on $\omega$ as $P_1,P_2,\dots,P_{2n}$ in clockwise order. Since every two of the original segments cross, and endpoints of non-crossing chords of $\omega$ would never cross inside, each of the $n$ segments must in fact join a point $P_i$ to the point $P_{i+n}$ exactly opposite it in this cyclic labeling (indices taken modulo $2n$ ): if a segment joined $P_i$ to $P_j$ with $j-i\ne n\pmod{2n}$ , its chord would fail to cross the chord joining some other pair, contradicting that every two segments cross.