1990 IMO Problems/Problem 2

Problem

Let $n\ge3$ and consider a set $E$ of $2n-1$ distinct points on a circle. Suppose that exactly $k$ 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 $n$ points from $E$. Find the smallest value of $k$ so that every such coloring of $k$ points of $E$ is good.

Solution

We form a graph on the $2n-1$ points by connecting two of these points iff one of the arcs they determine has exactly $n$ points in its interior. If $3\not|2n-1$, then this graph is a cycle, and the question becomes: what's the minimal $k$ s.t. whenever we color $k$ vertices of a cycle of length $2n-1$, there are two adjacent colored vertices? Obviously, the answer is $k=n$. On the other hand, when $3|2n-1$, the graph is a disjoint union of three cycles of length $\frac{2n+1}3$, and the answer will be, in this case, $3\cdot\left\lfloor\frac{2n-1}6\right\rfloor+1$.

This solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [1]

See Also

1990 IMO (Problems) • Resources
Preceded by
Problem 1
1 2 3 4 5 6 Followed by
Problem 3
All IMO Problems and Solutions