Library / /14 of 55

, 2016

Geometry Difficulty 8.5 Shortlist Prove it IMO

Let $n \geqslant 2$ be an integer. In the plane, there are $n$ segments given in such a way that any two segments have an intersection point in the interior, and no three segments intersect at a single point. Jeff places a snail at one of the endpoints of each of the segments and claps his hands $n-1$ times. Each time when he claps his hands, all the snails move along their own segments and stay at the next intersection points until the next clap. Since there are $n-1$ intersection points on each segment, all snails will reach the furthest intersection points from their starting points after $n-1$ claps.

a) Prove that if $n$ is odd then Jeff can always place the snails so that no two of them ever occupy the same intersection point.

b) Prove that if $n$ is even then there must be a moment when some two snails occupy the same intersection point no matter how Jeff places the snails.

Solution

(a) For odd $n$ , we travel along the circumference of the disk and mark each of the points $A_{i}$ or $B_{i}$ 'in' and 'out' alternately. Since every pair of lines intersect in the disk, there are exactly $n-1$ points between $A_{i}$ and $B_{i}$ for any fixed $1 \leqslant i \leqslant n$ . As $n$ is odd, this means one of $A_{i}$ and $B_{i}$ is marked 'in' and the other is marked 'out'. Then Jeff can put a snail on the endpoint of each segment which is closer to the 'in' side of the corresponding line. We claim that the snails on $l_{i}$ and $l_{j}$ do not meet for any pairs $i, j$ , hence proving part (a).

Without loss of generality, we may assume the snails start at $A_{i}$ and $A_{j}$ respectively. Let $l_{i}$ intersect $l_{j}$ at $P$ . Note that there is an odd number of points between $\operatorname{arc} A_{i} A_{j}$ . Each of these points belongs to a line $l_{k}$ . Such a line $l_{k}$ must intersect exactly one of the segments $A_{i} P$ and $A_{j} P$ , making an odd number of intersections. For the other lines, they may intersect both segments $A_{i} P$ and $A_{j} P$ , or meet none of them. Therefore, the total number of intersection points on segments $A_{i} P$ and $A_{j} P$ (not counting $P$ ) is odd. However, if the snails arrive at $P$ at the same time, then there should be the same number of intersections on $A_{i} P$ and $A_{j} P$ , which gives an even number of intersections. This is a contradiction so the snails do not meet each other.

(b) For even $n$ , we consider any way that Jeff places the snails and mark each of the points $A_{i}$ or $B_{i}$ 'in' and 'out' according to the directions travelled by the snails. In this case there must be two neighbouring points $A_{i}$ and $A_{j}$ both of which are marked 'in'. Let $P$ be the intersection of the segments $A_{i} B_{i}$ and $A_{j} B_{j}$ . Then any other segment meeting one of the segments $A_{i} P$ and $A_{j} P$ must also meet the other one, and so the number of intersections on $A_{i} P$ and $A_{j} P$ are the same. This shows the snails starting from $A_{i}$ and $A_{j}$ will meet at $P$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.