1990 IMO Problems/Problem 2
Let and consider a set of distinct points on a circle. Suppose that exactly of these points are to be colored black. Such a coloring is “good” if there is at least one pair of black points such that the interior of one of the arcs between them contains exactly points from . Find the smallest value of so that every such coloring of points of is good.
We form a graph on the points by connecting two of these points iff one of the arcs they determine has exactly points in its interior. If , then this graph is a cycle, and the question becomes: what's the minimal s.t. whenever we color vertices of a cycle of length , there are two adjacent colored vertices? Obviously, the answer is . On the other hand, when , the graph is a disjoint union of three cycles of length , and the answer will be, in this case, .
This solution was posted and copyrighted by grobber. The original thread for this problem can be found here: 
|1990 IMO (Problems) • Resources
|1 • 2 • 3 • 4 • 5 • 6
|All IMO Problems and Solutions