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]

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

Page

Toolbox

Search

1990 IMO Problems/Problem 2

Problem

Solution

See Also