Problem 2

Let

n\ge3

and consider a set

E

2n-1

distinct points on a circle. Exactly

k

points are black. Call the coloring good if some pair of black points has an arc whose interior contains exactly

n

points of

E

. Find the least

k

for which every coloring of

k

points is good.

Step 3 of 4: Bound black points by the independence number

Previous step Next step

\alpha(C_{2n-1})=n-1,\qquad \alpha\left(3C_{(2n-1)/3}\right)=n-2

Detailed analysis

A coloring with no good pair is an independent set in this graph. An odd cycle of length L has independence number (L-1)/2. Thus in the one-cycle case at most n-1 points can be black. In the three-cycle case, the total maximum is three times ((2n-1)/3-1)/2, which equals n-2.