IMO 1989 SL 29

Origin: ROM

Problem

A flock of 155 birds sit down on a circle C. Two birds Pi, Pj are mutually visible if m(PiPj) \leq10◦. Find the smallest number of mutually visible pairs of birds. (One assumes that a position (point) on C can be occupied simultaneously by several birds.)

Solution

Let Pi, sitting at the place A, and Pj sitting at B, be two birds that can see each other. Let k and l respectively be the number of birds visible from B but not from A, and the number of those visible from A but not from

B. Assume that k \geql. Then if all birds from B fly to A, each of them will see l new birds, but won’t see k birds anymore. Hence the total number of mutually visible pairs does not increase, while the number of distinct positions occupied by at least one bird decreases by one. Repeating this operation as many times as possible one can arrive at a situation in which two birds see each other if and only if they are in the same position. The number of such distinct positions is at most 35, while the total number of mutually visible pairs is not greater than at the beginning. Thus the problem is equivalent to the following one: (1) If xi \geq0 are integers with 35 j=1 xj = 155, find the least possible value of 35 j=1 (x2 j −xj)/2. If xj \geqxi + 2 for some i, j, then the sum of (x2 j −xj)/2 decreases (for xj −xi −2) if xi, xj are replaced with xi +1, xj −1. Consequently, our sum attains its minimum when the xi’s differ from each other by at most 1. In this case, all the xi’s are equal to either [155/35] = 4 or [155/35] + 1 = 5, where 155 = 20 \cdot 4 + 15 \cdot 5. It follows that the (minimum possible) number of mutually visible pairs is 20 \cdot 4\cdot3 2 + 15 \cdot 5\cdot4 2 = 270. Second solution for (1). Considering the graph consisting of birds as vertices and pairs of mutually nonvisible birds as edges, we see that there is no complete 36-subgraph. Turan’s theorem gives the answer immediately. (See problem (SL89-17).)