IMO 1990 SL 3

Origin: CZS

Problem

On a circle, 2n −1 (n \geq3) different points are given. Find the minimal natural number N with the property that whenever N of the given points are colored black, there exist two black points such that the interior of one of the corresponding arcs contains exactly n of the given 2n −1 points.

Solution

A segment connecting two points which divides the given circle into two arcs one of which contains exactly n points in its interior we will call a good segment. Good segments determine one or more closed polygonal lines that we will call stars. Let us compute the number of stars. Note first that gcd(n + 1, 2n −1) = gcd(n + 1, 3). (i) Suppose that 3 ∤n + 1. Then the good segments form a single star. Among any n points, two will be adjacent vertices of the star. On the other hand, we can select n −1 alternate points going along the star, and in this case no two points lie on a good segment. Hence N = n. (ii) If 3 | n + 1, we obtain three stars of / 2n−1 vertices. If more than / 2n−1 = n−2 points are chosen on any of the stars, then two of them will be connected with a good segment. On the other hand, we can select n−2 alternate points on each star, which adds up to n−2 points in total, no two of which lie on a good segment. Hence N = n −1. To sum up, N = n for 3 ∤2n −1 and N = n −1 for 3 | 2n −1.