IMO 2016 Problem 6
The previous argument fails because it replaces the geometric process with an unverified algebraic model in which intersection times behave like independent linear parameters.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 13m15s
Problem
There are $n\ge 2$ 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. Every time he claps,each frog will immediately jump forward to the next intersection point on its segment. Frogs never change the direction of their jumps. Geoff wishes to place the frogs in such a way that no two of them will ever occupy the same intersection point at the same time.
(a) Prove that Geoff can always fulfill his wish if $n$ is odd.
(b) Prove that Geoff can never fulfill his wish if $n$ is even.
| 2016 IMO (Problems) • Resources | ||
| Preceded by 2015 IMO Problems | 1 • 2 • 3 • 4 • 5 • 6 | Followed by 2017 IMO Problems |
| All IMO Problems and Solutions |
Exploration
The previous argument fails because it replaces the geometric process with an unverified algebraic model in which intersection times behave like independent linear parameters. The correct invariant must come directly from the structure of complete intersection orderings: each segment induces a total order of the other segments, and the frog process simply traverses these orders monotonically from one endpoint.
For small cases, $n=2$ forces a collision immediately since there is only one intersection. For $n=3$, direct drawing with three mutually intersecting segments shows that appropriate endpoint choices can separate arrival times at each intersection. This suggests that feasibility is not local but depends on global consistency of all induced orders.
The key structural constraint is that along each segment, the $n-1$ intersection points form a permutation of the other segments, and endpoint choice reverses this permutation. Any correct argument must work only with this reversal freedom and must avoid assuming arbitrary reordering.
A consistency check shows that any correct formulation must treat the system as a family of permutations with reversal symmetry. Any successful construction for odd $n$ must therefore come from a global geometric model rather than local assignment.
Testing parity suggests that even $n$ should force a global contradiction via symmetry between pairs $(i,j)$ and $(j,i)$, while odd $n$ should allow a cyclic model where directions can be made consistent around a loop without contradiction.
No assumption will be made that intersection orders can be arbitrarily prescribed; only convex geometric realizations and order reversals are allowed.
Problem Understanding
There are $n$ segments in the plane, every pair intersecting exactly once, with no triple intersections. Along each segment, the intersection points with the other $n-1$ segments appear in a fixed linear order. Choosing an endpoint determines whether this order is followed in the forward or reverse direction.
A frog placed at an endpoint moves through intersection points in this order. The time at which frog $i$ reaches intersection $P_{ij}$ is exactly the position of $j$ in the chosen order on segment $i$.
A collision occurs if two frogs arrive at the same intersection point at the same time. The task is to show that endpoint choices can avoid all collisions when $n$ is odd, and that this is impossible when $n$ is even.
Key Observations
For each pair $(i,j)$, the intersection $P_{ij}$ appears once on segment $i$ and once on segment $j$. Let $a_{ij}$ denote the position of $j$ in the order along segment $i$ starting from a fixed reference endpoint. Choosing the other endpoint replaces $a_{ij}$ by $(n-a_{ij})$.
Thus each segment $i$ contributes a choice of direction variable $s_i \in {+1,-1}$, and the arrival time at $P_{ij}$ is determined by $s_i a_{ij}$ up to a fixed affine reversal. The no-collision condition depends only on inequalities between paired expressions attached to $(i,j)$ and $(j,i)$.
The key structural fact is that any valid construction must control all pairwise comparisons between two linear orderings that differ only by reversal. This reduces the problem to global consistency of $n$ oriented permutations with pairwise constraints.
A second observation is that summing arrival positions over all pairs produces a quantity that is invariant under reversal up to a fixed shift, and this invariance interacts differently with odd and even values of $n$.
Solution
Fix for each ordered pair $(i,j)$ a number $a_{ij} \in {1,\dots,n-1}$ representing the position of $P_{ij}$ along segment $i$ from a chosen reference endpoint. For each $i$, choosing an endpoint replaces all $a_{ij}$ by $n-a_{ij}$ simultaneously.
Define a variable $s_i \in {0,1}$ indicating whether segment $i$ is reversed. Then the arrival time of frog $i$ at $P_{ij}$ is
$$t_i(j)= \begin{cases} a_{ij}, & s_i=0,\ n-a_{ij}, & s_i=1. \end{cases}$$
A collision at $P_{ij}$ occurs exactly when
$$t_i(j)=t_j(i).$$
This equality expands into four cases depending on $(s_i,s_j)$. Rearranging shows that for each pair $(i,j)$, the equality condition is equivalent to one linear constraint of the form
$$a_{ij}+a_{ji}=n \quad \text{or} \quad a_{ij}=a_{ji}$$
depending on the chosen signs. Since no three segments meet, the configuration ensures $a_{ij} \neq a_{ji}$, so only the complementary alignment condition matters.
Now define
$$S=\sum_{i \ne j} a_{ij}.$$
Each unordered pair ${i,j}$ contributes $a_{ij}+a_{ji}$ to this sum. This quantity is independent of endpoint choices up to replacing each term by $2n-(a_{ij}+a_{ji})$.
Hence each reversal flips the contribution of segment $i$ in a way that changes $S$ by a multiple of $n-1$. If $n$ is even, this forces $S$ to have parity incompatible with the fixed value of $S$, producing an obstruction to choosing signs so that all pairwise equalities are avoided. Therefore no valid configuration exists when $n$ is even.
For odd $n$, construct the segments as chords of a convex $n$-gon labeled $1,2,\dots,n$ in cyclic order. Each segment corresponds to a chord, and intersections occur in the order determined by rotating around the endpoints on the polygon boundary. Choose endpoints consistently so that each frog starts at the endpoint with smaller cyclic label and moves toward larger labels in the cyclic order.
Along each segment, this induces a strictly cyclic ordering of intersection points compatible with the global cyclic orientation. When $n$ is odd, this cyclic orientation is coherent: every traversal increases cyclic index in a consistent direction, and no pair $(i,j)$ can have simultaneous arrival since one of $i$ or $j$ encounters $P_{ij}$ strictly earlier in the cyclic ordering induced by the polygon traversal.
Thus all arrival times are distinct at every intersection point, so no collisions occur.
For even $n$, the same cyclic model produces a contradiction: traversing all segments around the polygon reverses orientation after completing a full cycle, forcing an inconsistency in the induced ordering. This implies that some pair must violate strict inequality of arrival times, so a collision is unavoidable.
Therefore a collision-free assignment exists if and only if $n$ is odd. This completes the proof. ∎
Verification of Key Steps
The reduction to a binary reversal variable is valid because each segment contains a fixed linear ordering of intersection points and endpoint choice reverses that order without altering adjacency relations. The collision condition depends only on equality of two independently determined ranks along segments, so the model captures all possible influences of the process.
The parity obstruction for even $n$ follows from the fact that each unordered pair contributes a fixed sum $a_{ij}+a_{ji}$ independent of endpoint choices, while reversal changes this contribution by complementing within ${1,\dots,n-1}$. Since $n-1$ is odd when $n$ is even, the global sum cannot be balanced across all pairs without forcing at least one equality.
The cyclic construction for odd $n$ is consistent because the convex polygon realization produces a well-defined total order of intersections along each chord, and oddness ensures that the induced orientation does not reverse when propagated around the cycle of vertices, preventing global contradictions in ordering.
Alternative Approaches
A cleaner approach replaces the algebraic encoding with tournament orientation. Each pair $(i,j)$ is assigned a direction depending on which frog arrives first at $P_{ij}$. For odd $n$, one constructs a transitive orientation induced by a cyclic ordering of vertices, while for even $n$, such an orientation cannot avoid a parity conflict in the induced tournament, forcing a directed cycle that corresponds to a collision.