30th IMO 1989 shortlist Problem 23 155 birds sit on a circle center O. Birds at A and B are mutually visible iff ∠AOB ≤ 10 o . More than one bird may sit at the same point. What is the smallest possible number of mutually visible pairs? Solution
: 270. Take 35 equally spaced points around the circle and place 5 birds at each of 15 points and 4 birds at the other 20 points. Only birds at the same point are mutually visible, so there are 15.10 + 20.6 = 270 mutually visible pairs. Suppose bird P is at A and bird Q is at B, where A and B are distinct but ∠AOB ≤ 10 o . Suppose that h birds are visible from A not B, and that k birds are visible from B not A. Without loss of generality h ≤ k. Now suppose all the birds at B move to A. Then the number of mutually visible pairs will not increase. By repeating this operation, we get to a configuration where two birds can see each other only if they are at the same point. Since the number of pairs has not been increased, it is sufficient to consider configurations where two birds can only see ach other if they are at the same point. Thus we may take 35 positions, labeled 1, 2, 3, ... , 35 and place x i birds at position i (we allow x i to be 0). So we wish to minimise ½ ∑ x i (x i - 1), or equivalently ∑ x i 2 , subject to ∑ x i = 155. Suppose two of the x i differ by more than 1, without loss of generality x 1 > x 2 + 1. Then (x 1 2 + x 2 2 ) - ( (x 1 - 1) 2 + (x 2 + 1) 2 ) = 2(x 1 - x 2 - 1) > 0. So in a minimising set of x i , the values can differ by at most 1. Thus the minimum is attained when 20 values equal 4 and 15 values equal 5. 30th IMO shortlist 1989 © John Scholes jscholes@kalva.demon.co.uk 28 Dec 2002 Last corrected/updated 28 Dec 02