We form a graph on the $2n-1$ points by connecting two of these points iff one of the arcs they determine has exactly $n$ points in its interior. If $3\not|2n-1$, then this graph is a cycle, and the question becomes: what's the minimal $k$ s.t. whenever we color $k$ vertices of a cycle of length $2n-1$, there are two adjacent colored vertces? Obviously, the answer is $k=n$. On the other hand, when $3|2n-1$, the graph is a disjoint union of three cycles of length $\frac{2n+1}3$, and the answer will be, in this case, $3\cdot\left\lfloor\frac{2n-1}6\right\rfloor+1$.

Take a look at this closed formula, which seems to confirm every such k. $k_{min}=\frac{2n-1- gcd(2n-1,n-2)+2}{2}$ I think I have a correct proof for the above formula, which is rather long but still uses the same elements of the very nice solution provided by grobber (graph theory, that is to say!) Cheers, Nick

You can easily see that the closed formula is the same as that of the first post (by Grobber) once you note that gcd (2n-1,n-2) = 1 or 3. It is 3 iff n is 2 mod 3.

We are considering the graph on these $2n-1$ vertices and we will join $2$ vertices iff there are exactly $n$ vertices between them (in any one of the 2 arcs).So in our graph every point has degree $2$. So it is the union of disjoint circle. Now if we mark the vertices $1,2,3,..2n-1$ then $1$ will be connected to $n+2$ $n+2$ will be connected to $2n+3$ i.e. $4$.So $1,4$ will in the same cycle. If $2n-1$ is not divisible by 3 the graph consists of only one circle.So the maximum number of independent set is $(2n-1)-1/2=n-1$.So if we colour $n$ vertices then the graph will have at least 2 consecutive coloured vertices and $k=n$ in this case. If $2n-1$ is divisible by 3 then the graph is union of 3 disjoint circles each of length $2n-1/3$.So the maximum number of independent set in each cycle is $f(n)=\frac{\frac{2n-1}{3} -1}{2}$.So total number of independent set is $3f(n)=n-2$ So in this case we need to colour $n-1$ vertex.

Cute problem

We consider the graph with the vertices being the points on the circle and two vertices are joined by an edge if they form an arc with $n$ points. Note that every vertex has degree $2$ so the graph is a union of disjoint cycles. Also notice that we can’t have $2$ adjacent colored vertices in a cycle. Now we will look for the number of cycles. Number the vertices from $1$ to $2n-1$ based on their position on the circle. We go from vertex $i$ to vertex $i+n+1$ $\pmod{2n-1}$ so if we have a cycle of length $k$ we need to have $$i+(n+1)k\equiv i \pmod{2n-1}\iff 2n-1\mid (n+1)k$$But note that $\text{gcd}(2n-1,n+1)\in \{1,3\}$ Case 1. $n\equiv 0\pmod 3$ Then we have a cycle of length $2n-1$ since the gcd is $1$, hence the answer is $n$. Case 2. $n\equiv 1\pmod 3$ Then we again have a cycle of length $2n-1$ so the answer is also $n$. Case 3. $n\equiv 2\pmod 3$ Then we have $3$ cycles of length $\frac{2n-1}{3}$ so the answer is $n-1$. $\square$