1989 IMO Sl #29

December 29th, 1979 is when my mom was born, and yesterday was her birthday. I am solving the 1989 IMO SL #29 in honor of her 🙂 (oops i forgot to do this yesterday). I would solve 1979 IMO SL #29, but it doesn't exist because there were only 26 problems for that shortlist. 

Happy Birthday Mama!

155 birds $ P_1, \ldots, P_{155}$ are sitting down on the boundary of a circle $ C.$ Two birds $ P_i, P_j$ are mutually visible if the angle at centre $ m(\cdot)$ of their positions $ m(P_iP_j) \leq 10^{\circ}.$ Find the smallest number of mutually visible pairs of birds, i.e. minimal set of pairs $ \{x,y\}$ of mutually visible pairs of birds with $ x,y \in \{P_1, \ldots, P_{155}\}.$ One assumes that a position (point) on $ C$ can be occupied simultaneously by several birds, e.g. all possible birds.

The answer is $\boxed{270}$. 

Let $P_i$, sitting at point $A$, $P_j$, sitting at point $B$, be two birds that are mutually visible. Denote $k,1$ to be the number of birds visible from $B$ but not $A$, and the number of birds visible from $A$ but not $B$. WLOG, assume that $k \ge l$. Then, if all birds at point $B$ move to point $A$, each of them will see $l$ new birds, but won't see the $k$ birds they saw from point $B$. Thus, the total number of mutually visible pairs does not increase after this movement, but the number of distinct positions occupied by at least one bird decreases by $1$. By repeating this operation, we will eventually reach a configuration in which two birds can see each other if and only if they are at the same point. Note that the number of such distinct positions is at most $35$. 

At this point, we can translate the given problem is equivalent to the following one. 

If $x_i \ge 0$ are integers with $$\sum_{i=1}^{35}x_i=155$$, find the least possible value of $$\frac{1}{2}\sum_{i=1}^{35}x_i(x_i-1).$$

Now we just have to solve this translated problem. 

We want to minimize $\sum_{i=1}^{35}x_i^2 - x_i$, or equivalently $\sum_{i=1}^{35}x_i$. Suppose that two of the $x_i$ differ by more than $1$, WLOG $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$$ if $x_1, x_2$ are replaced with $x_1-1, x_2+1$. Note that our sum achieves the minimum value when the $x_i$'s differ from each other by at most $1$. So, all the $x_i$'s are either $\lfloor \frac{155}{35} \rfloor = 4$ or $\lfloor \frac{155}{35} \rfloor + 1 = 5$, so that $155=20 \times 4 + 15 \times 5$. 

It follows that the minimum possible number of mutually visible pairs is $20(\frac{4\cdot 3}{2}) + 15(\frac{5 \cdot 4}{2})=270$, as desired. $\square$