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.
A: *

*The reason for finding $d = \gcd\{\,2n - 1, n + 1\,\}$ is that there are $2n - 1$ points and moving along an edge from one point to another in clockwise direction leaving $n$ points inside, you skip $n$ intervals, i. e. go to the $(n+1)$th next point. The last part means that remainder of the number of current point modulo $d$ doesn't change after one move. Therefore there are at least $d$ cycles. Suppose there are more than $d$ cycles. Then there is $r$, $0 \le r < d$ such that sequence $$(r + n + 1) \bmod (2n - 1), (r + 2n + 2) \bmod (2n - 1), \ldots, (r + kn + k) \bmod (2n - 1)$$
where $k = \frac{2n - 1}{d} - 1$
has at least one $r$. Let $(r + tn + t) \bmod (2n - 1) = r$. Then $t(n + 1) \bmod (2n - 1) = 0$, that means that $t \bmod \frac{2n - 1}{d} = 0$. But $0 < t \le k < \frac{2n - 1}{d}$. This contradiction proves that there are exactly $d$ cycles.

*It is easy to see that $C_k$ (a cycle on $k$ vertices) has an independent set of $\left\lfloor\frac{k}{2}\right\rfloor$ vertices with numbers $1, 3, \ldots, 2\left\lfloor\frac{k}{2}\right\rfloor - 1$. On the other hand at least two vertices in the set of $\left\lfloor\frac{k}{2} + 1\right\rfloor$ are adjacent by pigeonhole principle.

