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 4 of 4: Part (b): the parity clash for even

n

Previous step Next step

In plain words

When $n$ is even, every segment's two endpoints automatically share the same index-parity, splitting the $n$ segments into an odd-parity half and an even-parity half; but the placement was forced to be entirely one parity.

n\ \text{even} \Rightarrow\ \text{parity}(i)=\text{parity}(i+n)\ \Rightarrow\ \tfrac n2\ \text{segments both-odd},\ \tfrac n2\ \text{both-even}

Detailed analysis

By the previous step, the $n$ chosen starting points must all share one fixed parity of index — say, without loss of generality, they are exactly the $n$ odd-indexed points $P_1,P_3,\dots,P_{2n-1}$ (the even-indexed case is symmetric). Now, if $n$ is even, then for every $i$ the indices $i$ and $i+n$ have the same parity (adding an even number does not change parity). So each of the $n$ segments $\{P_i,P_{i+n}\}$ is either "both-odd" or "both-even" in its pair of indices, and exactly $\tfrac n2$ segments are both-odd while the other $\tfrac n2$ are both-even (as $i$ ranges over $1,\dots,n$ , exactly half are odd). But since $n\ge2$ is even, at least one segment is both-even, i.e. both $P_i$ and $P_{i+n}$ for that segment have even index — yet the frog on that segment must start at one of these two points, neither of which is odd-indexed, contradicting that every chosen starting point is odd-indexed. This contradiction shows that for even $n$ , no valid placement exists: Geoff can never fulfil his wish.