IMO 2016 · Problem 6

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 fulfil his wish if \(n\) is odd.

(b) Prove that Geoff can never fulfil his wish if \(n\) is even.

Official text of the problem. Official problem paper (PDF)

Solution

Choose coordinate axes so that none of the segments is vertical. Their supporting lines are pairwise nonparallel, so we may label them \[ \ell_i:\ y=m_i x+b_i,\qquad m_1<m_2<\cdots<m_n. \] Every intersection of two supporting lines lies on both original segments.

For \(i\ne j\), let \(r_i(j)\) be the position of \(\ell_i\cap\ell_j\) among the \(n-1\) intersections on \(\ell_i\), counted from left to right. These positions are distinct because no three lines meet at a point. A frog on segment \(i\) reaches this intersection at clap \[ r_i(j)\quad\text{if it faces right},\qquad n-r_i(j)\quad\text{if it faces left}. \]

We first establish three facts about these ranks.

Fix \(i<j\), and write \(P=\ell_i\cap\ell_j=(x_0,y_0)\). For any \(k\ne i,j\), put \[ d=m_kx_0+b_k-y_0. \] There are no triple intersections, so \(d\ne0\). The horizontal displacements from \(P\) to the intersections with \(\ell_k\) are \[ x(\ell_i\cap\ell_k)-x_0=\frac{d}{m_i-m_k}, \qquad x(\ell_j\cap\ell_k)-x_0=\frac{d}{m_j-m_k}. \] Consequently:

  • If \(k<i\) or \(k>j\), these intersections are either both to the left of \(P\) or both to its right.
  • If \(i<k<j\), exactly one of these intersections is to the left of \(P\).

Now \(r_i(j)-1\) and \(r_j(i)-1\) count the intersections to the left of \(P\) on the two lines. Each of the \(j-i-1\) intermediate-slope lines contributes exactly one to their sum, while every other line contributes zero or two. Hence \[ r_i(j)+r_j(i)\equiv j-i+1\pmod2. \tag{1} \] For consecutive slopes, every third line contributes equally to the two counts, giving \[ r_i(i+1)=r_{i+1}(i)\qquad(1\le i<n). \tag{2} \] For the smallest and largest slopes, every third line contributes exactly one to the sum, giving \[ r_1(n)+r_n(1)=n. \tag{3} \]

(a) Suppose \(n\) is odd. Place the frog on segment \(i\) facing right when \(i\) is odd and left when \(i\) is even.

Let \(t_i(j)\) be its arrival time at \(\ell_i\cap\ell_j\). Since \(n\) is odd, reversing direction changes the parity of the arrival time. Thus \[ t_i(j)\equiv r_i(j)+i-1\pmod2. \] For any \(i<j\), equation (1) yields \[ \begin{aligned} t_i(j)+t_j(i) &\equiv r_i(j)+r_j(i)+(i-1)+(j-1)\\ &\equiv (j-i+1)+(i-1)+(j-1)\\ &=2j-1 \equiv1\pmod2. \end{aligned} \] The two frogs therefore reach their common intersection at times of opposite parity, so they cannot collide. This holds for every pair, proving (a).

(b) Suppose \(n\) is even. Assume that some placement avoids all collisions.

By (2), frogs on segments \(i\) and \(i+1\) would collide if both faced right; they would also collide if both faced left. Thus consecutive segments in slope order must have frogs facing opposite directions.

Their directions must therefore alternate. Since \(n\) is even, the frogs on segments \(1\) and \(n\) face opposite directions. At their common intersection, their arrival times are either \[ r_1(n)\quad\text{and}\quad n-r_n(1), \] or \[ n-r_1(n)\quad\text{and}\quad r_n(1). \] In either case the two times are equal by (3), giving a collision. This contradiction proves (b), including the case \(n=2\).

The solution was checked against the official IMO shortlist solutions.