IMO 2000 SL G7

Origin: IRN | Category: Geometry

Problem

Ten gangsters are standing on a flat surface, and the distances between them are all distinct. At twelve o’clock, when the church bells start chiming, each of them fatally shoots the one among the other nine gangsters who is the nearest. At least how many gangsters will be killed?

Solution

The problem can be reformulated in the following way: Given a set S of ten points in the plane such that the distances between them are all distinct, for each point P \inS we mark the point Q \inS \ {P} nearest to P. Find the least possible number of marked points. Observe that each point A \inS is the nearest to at most five other points. Indeed, for any six points P1, . . . , P6 one of the angles PiAPj is at most 60◦, in which case PiPj is smaller than one of the distances APi, APj. It follows that at least two points are marked. Now suppose that exactly two points, say A and B, are marked. Then AB is the minimal distance of the points from S, so by the previous observation the rest of the set S splits into two subsets of four points according to whether the nearest point is A or B. Let these subsets be {A1, A2, A3, A4} and {B1, B2, B3, B4} respectively. Assume that the points are labelled so that the angles AiAAi+1 are successively adjacent as well as the angles BiBBi+1, and that A1, B1 lie on one side of AB, and A4, B4 lie on the other side. Since all the angles AiAAi+1 and BiBBi+1 are greater than 60◦, it follows that \angleA1AB + \angleBAA4 + \angleB1BA + \angleABB4 < 360◦. Therefore \angleA1AB + \angleB1BA < 180◦or \angleA4AB + \angleB4BA < 180◦. With- out loss of generality, let us assume the first inequality. On the other hand, note that the quadrilateral ABB1A1 is convex because A1 and B1 are on different sides of the perpendicular bisector of AB. From A1B1 > A1A and BB1 > AB we obtain \angleA1AB1 > \angleA1B1A and \angleBAB1 > \angleAB1B. Adding these relations yields \angleA1AB > \angleA1B1B. Similarly, \angleB1BA > \angleB1A1A. Adding these two inequalities, we get 180◦> \angleA1AB + \angleB1BA > \angleA1B1B + \angleB1A1A; hence the sum of the angles of the quadrilateral ABB1A1 is less than 360◦, which is a contradiction. Thus at least 3 points are marked. An example of a configuration in which exactly 3 gangsters are killed is shown below. 3† 6† 8†