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.
Problem
Source: IMO Shortlist 1989, Problem 29, ILL 89
Tags: combinatorics, graph theory, Extremal Graph Theory, Extremal combinatorics, IMO Shortlist
Number1
06.02.2013 22:36
Make graph $G'$ with 155 vertices(birds) like this: Two vertices (birds) are connected $\Leftrightarrow $ when they do not see each other. Therefore we have no clique $K_{36}'$ in graph. By Turan, we have \[\varepsilon' \leq {k-2\over 2(k-1)}\cdot n^2 -{r(k-1-r)\over 2(k-1)} = 11665\] where $k= 36$ and $r$ remainder if $n$ divide with $k-1$, so $r=15$. As we know upon Turan configuration with $\varepsilon' = 11665$ exist, smallest number of bird pairs seeing each other is 270.
NoYoo-hooForMe
09.02.2013 19:52
Number1 wrote: As we know upon Turan configuration with $\varepsilon' = 11665$ exist, smallest number of bird pairs seeing each other is 270. Isn't it necessary to actually exhibit an arrangement of birds achieving the minimum of $270$? Just because Turan guarantees a graph satisfying a particular property exists, it doesn't necessarily follow that there is an arrangement of birds corresponding to that graph. Fortunately it is not hard to give a specific arrangement of birds. Divide the birds into $35$ groups and place the groups equidistant on the circle--so each group is separated by just over $10$ degrees of arc and the birds can see only other birds in the same group. There will be $20$ groups of $4$ birds and $15$ groups of $5$ birds ($20*4+15*5=155$). The total number of bird pairs that can see each other is thus: $20\dbinom{4}{2}+15\dbinom{5}{2}=270$.
skyletter
06.07.2016 19:53
But if we use the result https://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem. We have $|E|\le \lfloor \frac {k-1}{2k}n^2 \rfloor=11669$,which is not $11665$,could someone explain why this happens?Confused.THANKS
rashah76
21.12.2018 19:24
NoYoo-hooForMe wrote: Number1 wrote: As we know upon Turan configuration with $\varepsilon' = 11665$ exist, smallest number of bird pairs seeing each other is 270. Isn't it necessary to actually exhibit an arrangement of birds achieving the minimum of $270$? Just because Turan guarantees a graph satisfying a particular property exists, it doesn't necessarily follow that there is an arrangement of birds corresponding to that graph. Fortunately it is not hard to give a specific arrangement of birds. Divide the birds into $35$ groups and place the groups equidistant on the circle--so each group is separated by just over $10$ degrees of arc and the birds can see only other birds in the same group. There will be $20$ groups of $4$ birds and $15$ groups of $5$ birds ($20*4+15*5=155$). The total number of bird pairs that can see each other is thus: $20\dbinom{4}{2}+15\dbinom{5}{2}=270$. Turan s graph has maximum no of edges no containing K36 in this case. notice each edge denotes a bird pair not seeing each other . there are 155*154/2 pairs of birds out of which at most maximum 11669 pairs are not mutually visible. hence the min pairs that are always visible are 155*154/2 - 11669 =266 pairs.