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 2 of 4: Determine the cycle decomposition

Previous step Next step

\gcd(n-2,2n-1)=\gcd(n-2,3)

Detailed analysis

The graph is generated by repeatedly adding n-2 modulo m, so it is a union of cycles. Since $\gcd(n-2,2n-1)=\gcd(n-2,3)$ , it is one cycle of length $2n-1$ when $n\not\equiv2\pmod3$ . When $n\equiv2\pmod3$ , it is three cycles, each of length $(2n-1)/3$ .