155 birds sit on a circle center O. Birds at A and B are mutually visible iff ∠AOB ≤ 10o. More than one bird may sit at the same point. What is the smallest possible number of mutually visible pairs?
Solution
Answer: 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 ≤ 10o. 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 xi birds at position i (we allow xi to be 0). So we wish to minimise ½ ∑ xi(xi - 1), or equivalently ∑ xi2, subject to ∑ xi = 155. Suppose two of the xi differ by more than 1, without loss of generality x1 > x2 + 1. Then (x12 + x22) - ( (x1 - 1)2 + (x2 + 1)2) = 2(x1 - x2 - 1) > 0. So in a minimising set of xi, the values can differ by at most 1. Thus the minimum is attained when 20 values equal 4 and 15 values equal 5.
© John Scholes
jscholes@kalva.demon.co.uk
28 Dec 2002
Last corrected/updated 28 Dec 02