MathLabs

Problem 6

There are n≥2n\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−1n-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 nn is odd. (b) Prove that Geoff can never fulfil his wish if nn is even.
Step 3 of 4: Part (b): the necessary shape of any valid placement
Previous stepNext step
In plain words

If two frogs start at consecutive points on the circle, their very first jump already collides; if they start at opposite ends of the same segment, that segment collides with itself.

no two frogs at adjacent Pi, none at antipodal Pi,Pi+n\text{no two frogs at adjacent }P_i,\ \text{none at antipodal }P_i,P_{i+n}
Detailed analysis

Suppose, for contradiction, that some placement of the nn frogs (one per segment, i.e. one at each pair {Pi,Pi+n}\{P_i,P_{i+n}\}, choosing one of the two) avoids all collisions. One checks that frogs cannot be placed at two cyclically consecutive points Pi,Pi+1P_i,P_{i+1} (their first intersection points would coincide immediately), so the nn chosen starting points must alternate around the circle; combined with there being nn of them among 2n2n positions, they must occupy every other position exactly, i.e. positions of a single fixed parity. But no two frogs can be placed at a diametrically opposite pair Pi,Pi+nP_i,P_{i+n} either, since PiP_i and Pi+nP_{i+n} are the two endpoints of the very same segment, and only one frog is placed per segment.