Q:

An IMO graph theory problem

In the second 1990 IMO problem, I saw a solution (probably of the proposer) as follows, of which I have some questions. 
Problem 2: Suppose $n\geq 3$, and let $S$ be a set of $2n-1$ distinct points on a circle. Assume that exactly $k$ points of $S$ are colored black. A coloring of $S$ is called "good" if there is at least one pair of the black points such that the interior of one of the arcs between the pair contains exactly $n$ points of $S$. Find the least value of $k$ so that each coloring of $S$ be "good".
Solution: We call two points "dependent" if exactly $n$ points of $S$ sits in one of the arcs between these two points. We need to determine the least value of $k$ with the property that each $k$ points of $S$ contain at least one pair of dependent points. Connecting any pair of dependent points, there obtains a graph $G$ with degree $2$ at each vertex. $G$ is formed of disjoint cycles. We consider two cases:
A) If $(3,2n-1)=1$, then $(2n-1,n+1)=(2n-1,3)=1$, whence $G$ is itself a cycle. In this case, "obviously" the least value for $k$ is $\lbrack \frac{2n-1}{2} \rbrack +1=n$.
B) If $(3,2n-1)=3$,then $(2n-1,n+1)=3$, i. e. there are $3$ cycles in $G$ each having $\frac{2n-1}{3}$ vertices. In this case, the least value of $k$ would be $$3\left\lbrack \frac{\left(\frac{2n-1}{3}\right)}{2}\right\rbrack+1=3\left(\frac{\left(\frac{2n-1}{3}\right)}{2}-\frac{1}{2}\right)+1=n-1.$$
My question:
1) Why do we compute the "gcd" of $2n-1$ and $n+1$? (That is, what does this "gcd" have to do with the number of cycles?)
2) In each of the cases, I don't understand why do we compute the "bracket" of $\frac{2n-1}{2}$ plus $1$, or the "bracket" of $\frac{\frac{2n-1}{3}}{2}$ plus $1$, respectively?
Thanks for any elucidating answer!

A:

If you label the points with $\mathbb Z/(2n-1)\mathbb Z$ in order, then node $x$ is adjoined to nodes $x+n+1$ and $x-(n+1)$. So the nature of the graph depends on the sequence:
$$0,n+1,2(n+1),\dots,$$
Two nodes $a,b$ in the graph are in the same loop if $a-b=(n+1)A$ for some $A$. But the number of distinct multiples of $n+1$ in $\mathbb Z/(2n-1)\mathbb Z$ is equal to $\frac{2n-1}{\gcd(2n-1,n+1)}$.
Since each cycle has $\frac{2n-1}{\gcd(2n-1,n+1)}$ nodes, there must be $\gcd(2n-1,n+1)$ cycles.
But we have that $\gcd(2n-1,n+1)\mid 3$. 
Now, in a cycle graph of size $M$, we can paint $\left\lfloor\frac{M}{2}\right\rfloor$ of them  black before we have two connected nodes that are black. If you paint more than $\left\lfloor\frac{M}{2}\right\rfloor$, then two black nodes are connected by an edge.
So the most you can color black without getting an edge with two black nodes:
$$\gcd(2n-1,n+1)\left\lfloor{\frac{2n-1}{2\gcd(2n-1,n+1)}}\right\rfloor$$
So the smallest $k$ which guarantees an edge with two black nodes is one more than this.

