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 4 of 4: Read off the sharp threshold

Previous step Next step

k_{\min}=\begin{cases}n,&n\equiv0,1\pmod3,\\n-1,&n\equiv2\pmod3,\end{cases}

Detailed analysis

The independent sets of the stated sizes exist by taking alternating vertices on each odd cycle, so the bounds are sharp. Therefore $k_{\min}=n$ when $n\equiv0,1\pmod3$ , and $k_{\min}=n-1$ when $n\equiv2\pmod3$ .