41st IMO 2000 shortlist Problem G7 Ten gangsters are standing in a field. The distance between each pair of gangsters is different. When the clock strikes, each gangster shoots the nearest gangster dead. What is the largest number of gangsters that can survive? Solution
: 7. Obviously at least two gangsters die: someone must get shot, but he must shoot someone else. It is easy to arrange for just four to die. Take four roughly in a circle around a fifth. All four shoot the gangster in the center, and he shoots one of those in the circle. So two out of the five die. Arrange the other five similarly, some distance away. However, with a little care, we can reduce that to three gangsters dying, by arranging that the two central gangsters both shoot the same gangster. Consider the situation below. The lh circle is slightly smaller than the rh circle. The angles 142, 243, 7 10 8, 9 10 8 are slightly greater than 60 o . The distance 56 is the same as the radius of the larger circle. Thus 1, 2, 3 and 5 shoot 4; 4, 6 and 10 shoot 5; 7, 8 and 9 shoot 10. So 4, 5, 10 die and the others survive. So we have to show that we cannot have just two gangsters die. It is surprisingly difficult. We cannot have six gangsters all shooting the same person. For suppose A, B, C, D, E, F all shoot O. Suppose ∠AOB ≤ 60 o . Since OA and OB are assumed to be unequal, angles OAB and OBA are unequal. Hence at least one of them > 60 o . Suppose it is ∠OAB. Then ∠OAB > ∠AOB, then OB > BA, so B should shoot A not O. Contradiction. Similarly, if ∠OBA > 60 o . So ∠OAB > 60 o . Similarly, each of the other angles BOC, COD, DOE, EOF, FOA must be > 60 o . But the sum of the six angles is 360 o . Contradiction. So at most 5 gangsters can shoot the same person. So assume that it is possible to arrange 10 gangsters so that only two die. Let A and B be the two closest gangsters. Then they must shoot each other. So we have to show that every other gangster shoots A or B. Since at most 5 gangsters can shoot the same person, 4 of the others must shoot A and 4 must shoot B. Using the result in the previous paragraph if C is the next gangster anticlockwise from B who shoots A and C' the next gangster clockwise then, the ∠CAC'  AC). Similarly ∠GBA = a + ∠ADB  ∠HAB + ∠GBA > 180 o . Similarly, ∠ECD = d + ∠CAD > 2d (since CD > CA) and ∠FDC = c + ∠DBC > 2c, so 2c + 2d < ∠ECD + ∠FDC < 180 o . Hence c + d < a + b. Contradiction, since they are obviously equal. 41st IMO shortlist 2000 © John Scholes jscholes@kalva.demon.co.uk 10 Oct 2002