Coloring the all the natural numbers upto $n$

Question

Problem(IMO 1985 P2): Let $n$ and $k$ be relatively prime positive integers with $k<n$. Each number in the set $M=\{1,2,3,\ldots,n-1\}$ is colored either blue or white. For each $i$ in $M$, both $i$ and $n-i$ have the same color. For each $i\ne k$ in $M$ both $i$ and $|i-k|$ have the same color. Prove that all numbers in $M$ must have the same color.

My Progress: Consider any natural number $i<n$. Then we know that $(i,n-i,|i-k|)$ have the same color. I considered $(i,n-i,|i-k|)$ as a vector so it represents a point in Cartesian space with positive integer coordinates. So we are considering $(n-2)$ such points. We say that two points are connected iff the vectors have at least one component common(So $(1,11,4)$ and $(4,8,1)$ are connected). And we intend to prove that all this points are of the same color or in graph theoretic analog we want to prove that the graph $G$ with $V(G)=n-2$ is connected. And this where I am stuck. I have been able to prove that all the vertices have degree at least $2$. But this is not enough to prove that the graph is connected.

So in short: I need help to prove that the graph is connected.

Please don't give out the solution, rather give me hints first.

Thank you.

Answer 1

I just pulled out my original solution as submitted back then in Joutsa, Finland:

We define $s\sim t$ to mean that $s$ and $t$ have the same colour

Lemma. If $s,t\in\{1,\ldots,n-1\}$ with $t-s\equiv k\pmod n$, then $s\sim t$.

Proof.
First consider the case $k+1\le t\le n-1$, i.e., $s=t-k$, $1\le s\le n-1-k$:
Then $|k-t|=t-k=s$ (because $k-t<0$), i.e., $t\sim s$ (as $t\ne k$)

Now consider $1\le t\le k-1$, i.e., $s=t-k+n$, $n+1-k\le s\le n-1$ (which is only possible if $k\ge 2$, by the way).
Then $s\sim n-s$ and (as $t\ne k$) $t\sim|k-t|$.
But $|k-t|=|n-s|=n-s$ (because $s=t-k+n$ and $n-s>0$), i.e., $t\sim n-s$.
As $\sim$ is clearly an equivalence relation, this case also leads to $t\sim s$.

Above we covered all possible values for $t$, except $t=k$.
However, that case is excluded as $t=k$ and $t-s\equiv k\pmod n$ would mean $s\equiv 0\pmod n$, which is absurd. $\square$

Now note that the $n$ integers $0,k,2k,\ldots, (n-1)k$ are pairwise incongruent $\bmod n$ (for $ak\equiv bk\pmod n$ together with the given co-primeness implies $a\equiv b\pmod n$).
In particular, none of the $n-1$ numbers $k, 2k, 3k, 4k, \ldots, (n-1)k$ is $\equiv 0\pmod n$.
Therefore, these numbers $\bmod n$ are a permutation of $\{1,\ldots,n-1\}$. By the lemma above, we conclude$$k\sim 2k\bmod n\sim 3k\bmod n\sim\ldots \sim (n-1)k\bmod n, $$i.e., all $n-1$ numbers have the same colour.

qed