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 1 of 4: Encode the condition as a graph

Previous step Next step

m=2n-1,\qquad i\sim j\Longleftrightarrow j-i\equiv\pm(n-2)\pmod m

Detailed analysis

Label the points cyclically by integers modulo $m=2n-1$ . Two points have an arc with exactly n interior points precisely when their labels differ by $\pm(n-2)\pmod m$ (the two directions have differences n-2 and n+1). Join exactly these pairs. Then a good coloring is exactly a coloring containing an edge with both endpoints black.