It is given $n$ a natural number and a circle with circumference $n$. On the circle, in clockwise direction, numbers $0,1,2,\dots n-1$ are written, in this order and in the same distance to each other. Every number is colored red or blue, and there exists a non-zero number of numbers of each color. It is known that there exists a set $S\subsetneq \{0,1,2,\dots n-1\}, |S|\geq 2$, for wich it holds: if $(x,y), x<y$ is a circle sector whose endpoints are of distinct colors, whose distance $y-x$ is in $S$, then $y$ is in $S$. Prove that there is a divisor $d$ of $n$ different from $1$ and $n$ for wich holds: if $(x,y),x<y$ are different points of distinct colors, such that their distance is divisible by $d$, then both $x,y$ are divisible by $d$.
Problem
Source: 2019 Serbia TST Day 1 P3
Tags: combinatorics, number theory
Pajaraja
31.05.2019 22:25
Here's my solution from the contest. Quite a fun problem. Obviously, we can reinterpret this problem as numbers$\mod n$. If we work in the group of residues$\mod n$, some of these numbers are red, and some are blue, and for every $y\in S$, we know that $x$ and $x+y$ are of the same color, or $x+y\in S$. We shall consider all arithmetic operations$\mod n$, unless specifically stated otherwise. Now we can move forward to the actual proof. Denote the elements of set $S$ as $a_1,a_2,\cdots,a_k$. Let $d=GCD(n,a_1,a_2,a_3,\cdots,a_k)$. Since $|S|\ge2$, $S$ has at least one non-zero element, hence we know that $d\ne n$. Now we consider the following cases: $\textit{Case 1: } d\ne 1.$ We shall prove that this $d$ is an adequate choice for the $d$ requested in the problem statement. To prove that, we shall prove that if $d\nmid x$, then $x$ and $x+d$ are of the color. By inductive application of the Euclidian algorithm, we know that there's a linear combination of integers $c_1,c_2,\cdots,c_k,c_{k+1}$, such that $c_1a_1+c_2a_2+\cdots+c_ka_k+c_{k+1}n=d$ (this equation is viewed in $\mathbb{Z}$, not$\mod n$). Now we can deduce that there's a linear combination of the elements from $S$, with nonnegative coefficients that give us a number that is $\equiv d\pmod n$ (by removing $c_{k+1}$ and taking $c_1,c_2,\cdots,c_k$ modulo $n$).Now if we take a number $x$ such that $d\nmid x$, we know that $d\nmid x+a_i$, and that $x$ and $x+a_i$ are of the same color. So by successively adding the elements of our linear combination to get a number that is $\equiv d\pmod n$ we know that we shall always obtain a number that is not divisible by $d$, and colored with the same color as $x$. (this means that for any selection of $i_1,i_2,\cdots,i_t$ we know that if $d\nmid x$, then $x$ and $x+a_{i_1}+a_{i_2}+\cdots+a_{i_t}$ are of the same color). Using this fact, we know that if $d\nmid x$, then $x$ and $x+d$ are of the same color, meaning that if $d|x-y$, and that they're of different colors, then $d|x$, which is what we set out to prove. $\textit{Case 2: } d=1$. Denote by $b_1,b_2,\cdots, b_p$ the blue elements of $S$, and by $r_1,r_2,\cdots,r_q$ the red elements of $S$. Now we observe a trivial, yet crucial fact: $b_i+r_j\in S$. This holds true because if it weren't true then $b_i$ and $b_i+r_j$ would be the same color, but so would $r_j$ and $b_i+r_j$, which is an obvious contradiction. Now as in the previous case we know that there's a linear combination of $b_1,b_2,\cdots,b_p,r_1,r_2,\cdots,r_q$ with nonnegative coefficients such that $f_1b_1+f_2b_2+\cdots+f_pb_p+g_1r_1+g_2r_2+\cdots+g_qr_q\equiv1\pmod n$. Chose such a linear combination so that $f_1+f_2+\cdots+f_p+g_1+g_2+\cdots+g_q$ is minimal. Now if there exist $1\le u \le p$ and $1\le v\le q$ so that $f_u>0$ and $g_v>0$, then we can replace $b_u+r_v$ with one element from $S$, thus reducing the sum of coefficients in our linear combination, which contradicts the minimality of the chosen combination. This means that a number that is $\equiv1\pmod n$ that can be expressed as the sum of only blue elements from $S$, or only red elements of $S$. WLOG assume that the blue set satisfies this claim. Our next goal is to prove that if $x\not\in S$, then $x$ is colored blue. As there exists a linear combination of the blue elements of $S$ which gives $1\pmod n$, then by multiplying this linear combination by $x$, we get a linear combination of these numbers that satisfy $z_1b_1+z_2b_2+\cdots+z_pb_p\equiv x\pmod n$. We write this as $b_{i_1}+b_{i_2}+\cdots+b_{i_l}\equiv x\pmod n$, for some, not necessarily distinct, $i_k$. We now denote $s_w=b_{i_1}+b_{i_2}+\cdots+b_{i_w}$. Let $h$ be the largest number such that $s_h\in S$. Since for $j\ge h$, we know that $s_{j+1} -s_j\in S$ and $s_{j+1}\not\in S$, we have that $s_j$ and $s_{j+1}$ are of the same color. This means (inductively) we obtain that $s_l$ and $s_h$ are of the same color. However, we know that $s_h$ mustn't be red, as then it would be equal to some $r_d$, but then $r_d+b_{i_{h+1}}=s_{h+1}\not\in S$, which is a contradiction. This means that $s_h$ is blue, and then so is $x=s_l$. Now chose $d'=GCD(n,r_1,r_2,\cdots,r_q)$. We shall prove that this is the required $d$ from the problem statement. Since every red point is in $S$, we know that there's at least one non-zero number in the set ${r_1,r_2,\cdots,r_q}$, which means $d'\ne n$. If $d'=1$, then we would be able to obtain $1\pmod n$, and by extension every number$\mod n$, as a linear combination of these red numbers. However, using the same proof as before, this would mean that every number not in $S$ would also be colored red, but as $S$ is not the whole set $\{0,1,2,\cdots,n-1\}$, this is not possible. Now we know that if $d'\nmid x$, then $x$ is blue, meaning that if $d'|x-y$, and $x,y$ are different colors, then at least one of them is red so $d'|x,y$. This proves that this choice of $d$ checks out, and finishes our proof. $\textit{Comment: }$ I am not sure whether it is actually possible to construct an example that satisfies all the conditions from the problem statement when $d=1$, but this can't be hard to prove or disprove given the strength of the claim found in this solution (that all number outside of $S$ are the same color, and that all the red numbers have greatest common divisor greater than $1$). However, to avoid discussing possibly boring modular algebra we construct a fitting $d$, without checking whether the set exists. On the other hand such a set $S$ in our first case is trivial to construct with $d|x \iff x\in S$.
alexiaslexia
16.05.2021 09:42
Probably the problem I've been most invested with recently. Personally, the problems I enjoy most have a multi-dimensional approach to it; it's due to those gems that the lines between the four subjects of Algebra, Combo, NT and Geo are blurred so that using an extremal technique in an NT problem does not seem out of place.
Notes. The only missing element here is geo; but $\textsf{all of the three}$: combinatorial graphs, almost-Cauchy-Davenport additive sets and plain $\text{mod} \ n$ matchings has a Section in this Solution dedicated to them.
Also, this is one of the only times I've conjured a fairly lengthy Solution with Sections varying wildly among each other.
Now, let's get the obvious NT part out of the bag (there will be more non-obvious stuff at the end!)
Easy and skippable Claim.$\color{green} \rule{5.7cm}{2pt}$
$\color{green} \clubsuit$ $ \boxed{\textbf{Basic Additive Refreshers.}}$ $\color{green} \clubsuit$
$\color{green} \rule{5.7cm}{2pt}$
We Claim that for every set of integers $\{s_1,s_2,\ldots,s_{|S|}\}$ so that
\[ \gcd{(s_1,s_2,\ldots,s_{|S|},n)} = d \]we can find coefficients $c_1,c_2,\ldots,c_{|S|}$ so that
\[ \sum_{i = 1}^{|S|} c_is_i \equiv d \pmod n \]
As a Corollary, applying this Lemma to the problem when $d \ne 1$ gives us $x$ and $x+d$ being the same color for every $d \ne x$; as we can be sure that
\[ x+\sum_{i = 1}^{|S|} a_is_i \not\in S, \ \text{as} \ \text{LHS} \equiv x \ \text{mod} \ d\]for every $a_i \geq 0$ (therefore no harm is done on constructing the desired $x+d$ using the problem assertion $\sum_{i=1}^{|S|} c_i$ times.)
$\color{green} \rule{25cm}{0.2pt}$
$\color{green} \spadesuit$ $ \boxed{\textbf{Proof.}}$ $\color{green} \spadesuit$
We use induction (the case $|S| = 1$ is just Euclidean Algo.) Suppose it is true for $k = |S|$. This means we can find coefficients $c_1$ to $c_{|S|}$ so that
\[ \sum_{i = 1}^{|S|} c_is_i \equiv d_{S} \pmod n \]where $d_S$ is the gcd with $S = \{s_1,\ldots,s_{|S|}\}$.
For $k = |S|+1$, let the new $S'$ to be $\{s_1,\ldots,s_{|S|}\} \cup \{t\}$. So, the gcd of the new set is $(d_S,t) = d_{S'}$. By Euclidean Algo, we can find coefficients $l$ and $m$ so that
\[ ld_S + mt = d_{S'} \](without $\text{mod} \ n$ here)
Now, setting $c_i' = l \cdot c_i$ and $c_{|S|+1}' = m$ we can verify that the Claim holds true. We are done.
Note that on the second part of the Claim, since $|S| \geq 2$, $d$ cannot be $n$, as there must be at least one nonzero term among $\{s_1,s_2,\ldots,s_{|S|}\}$.
Now for the extremely exhausting part. Let $d = 1$; and further separate the members of $S$ into $A$ and $B$; where the members of the set $A$ are $\textit{forced and fixed}$ to wear an attribute of color $A$, likewise with $B$.
Next, consider the remaining numbers (sometimes referred to as the $\textit{attacking}$ numbers later) to be in the set
\[ E = \{0,1,\ldots,n-1\} - S \]After this Claim, we will show that $E$ can be forcefully attired into two sets $E_A$ and $E_B$ which behaves (almost) similarly to $A$ and $B$.
$\color{magenta} \rule{8.5cm}{2pt}$
$\color{magenta} \clubsuit$ $ \boxed{\textbf{Extremal Chaining: Twofold Separation.}}$ $\color{magenta} \clubsuit$
$\color{magenta} \rule{8.5cm}{2pt}$
The core idea of this proof is minimal chaining: if we'd like to state an $\textit{attacking number}$ to one particular color, it's almost best to do so with the most uncomplicated way possible. It can be proven that said chaining is indeed free of roadblocks.
Formally, let the $\textsf{minimal}$ representation of some attacking number $e$ to be
\[ e \equiv \sum_{i=1}^{|S|} c_is_i \pmod n\]where
this representation exists, since $1$ has a representation by $\color{green} \clubsuit$ $ \boxed{\textbf{Basic Additive Refreshers}}$ $\color{green} \clubsuit$; and
minimal meaning to choose the representation with the minimal $\sum_{i=1}^{|S|} c_i$. If there are more than one, we take the liberty and shamelessness of $\color{magenta} \text{considering them all}$ (more on this after this Section.)
Then, $e$ can be $\color{magenta} \textbf{\textit{chained down}}$ all the way into $s_1$; in other words, we will prove that $e$ has the same color as $d_1$.
$\color{magenta} \rule{25cm}{0.2pt}$
$\color{magenta} \spadesuit$ $ \boxed{\textbf{Proof.}}$ $\color{magenta} \spadesuit$
We will first elaborate on the meaning of $\textit{attacking}$ and $\textit{chaining down}$. While the problem says that if $y-x \in S$ and $x,y$ having different colors imply $y \in S$, we turn this into its contrapositive: if $y \not\in S$ (a.k.a. $y$ is an attacking number) and $s \in S$, then $y-s$ has the same color as $y$.
A natural continuation of this is to tone down the lingo of $y-s$ having the same color: we can exploit that if, again $y-s \not\in S$ and $t \in S$, then $y-s-t$ has the same color as both $y-s$ and $y$. Here, we can say that $\textbf{both}$ $y-s$ and $y-s-t$ are $\textit{chained down}$ from $y$.
Back to the Lemma: let $e$'s representation is as shown in the Lemma. Since the only way for $e$'s chaining down to $s_1$ to fail is if some $e'$ in the middle with
\[ e' = \sum_{i=1}^{|S|} c_i's_i \pmod n\]is an element of $S$, then we can replace the terms in $e'$ altogether with $e'$ itself and form
\[ e = e'+ \sum_{i=1}^{|S|} (c_i-c_i')s_i \pmod n\]as its more minimal representation. This is certainly not happening, so the imaginary term $e'$ cannot exist (this is almost equivalent to the $s_w$ argument above.)
Corollary for the end of the Second Part.If $a \in A$ and $b \in B$; then the number $a+b$ must $\textbf{\textit{not}}$ be an attacking number, or else its minimal representation must have length $2$ (with $a+b$ being one of them) --- implying that $a+b$ can both be chained down to $a$ and $b$.
This will directly result in a contradiction, as $a$ and $b$ cannot have the same color (as $a+b$.)
We are done for the first part. $\blacksquare$
The second part (discussing sets $E_A$ and $E_B$ specifically) of this Solution will be divided into two parts:
First, we present a transitory Claim which is closely related to $\color{magenta} \clubsuit$ $ \boxed{\textbf{Extremal Chaining: Twofold Separation}}$ $\color{magenta} \clubsuit$ with focusing on one set.
$\color{red} \rule{6.3cm}{2pt}$
$\color{red} \clubsuit$ $\color{red} \boxed{\textbf{C Part: Additive-Magnitude.}}$ $\color{red} \clubsuit$
$\color{red} \rule{6.3cm}{2pt}$
Define the $\textit{size}$ of an attacking number to be (the obvious) coefficient sum. Then, if $e \in E_A$, then $e-b$ ($b \in B$) also belongs to $E_A$, and furthermore, their sizes are equal.
$\color{red} \rule{25cm}{0.2pt}$
$\color{red} \spadesuit$ $\color{red} \boxed{\textbf{Proof.}}$ $\color{red} \spadesuit$
The first part is obvious: if $e-b \in A, B$ or $E_B$, then $e \in S, E_B, E_B$ respectively.
The second part is proven $\color{red} \textit{from the top}$. Consider $e \in E_A$ with maximal size: it must attack another element of $E_A$ with a size equal or more than it, or else $e$ can be represented with terms of $S$ using both colors, using a size equal or less than it.
Since there is no term from $E_A$ with a size greater than $e$, all $\textit{maximal sized}$ elements must attack maximal sized ones too. Having proven that the top $k$ levels behave this way, consider an element $e$ from the $k+1^{\text{th}}$ level.
Again, it cannot attack a lower-sized element, but all the upper parts have been attacked by a beast in their level. This cannot warrant the $k+1^{\text{th}}$ sized-element to attack a higher-sized, else the higher-sized will have two attackers (which must not happen, as two elements from two different levels are never equal.) We are done.
Note that here we use the shamelessness of $\color{magenta} \text{considering all representations}$ of $e$ mentioned earlier in $\color{magenta} \clubsuit$ $ \boxed{\textbf{Extremal Chaining}}$ $\color{magenta} \clubsuit$. More explicitly, the almost more innocent representation of $e$ in all elements of $A$ can $\textit{in fact be overshadowed}$ by a misdirected attack towards an element one level below it.
Next, we exclusively consider relevant appearances in the second level (from the bottom).
$\color{red} \rule{8.65cm}{2pt}$
$\color{red} \clubsuit$ $\color{red} \boxed{\textbf{A/N Part: Set Theory Commercial Break.}}$ $\color{red} \clubsuit$
$\color{red} \rule{8.65cm}{2pt}$
Either $E_A$ or $E_B$ is empty.
$\color{red} \rule{25cm}{0.2pt}$
$\color{red} \spadesuit$ $\color{red} \boxed{\textbf{Proof.}}$ $\color{red} \spadesuit$
Call an element of $A$ $\color{red} \textit{relevant}$ if it appears at least once among the summation of the elements of $E_A$ (similarly with $B$.)
If the Lemma is false, then there are relevant members of both $A$ and $B$. Unlike the shameless plugging earlier, here we only consider one relevant pair of numbers: $a_r$ and $b_r$. We will prove, by a lucky break, that
\[ a_r+b_r \in A \cap B \]Now consider an element of $E_A$ with $a_r$ in its representation. By an argument similar to the second paragraph of $\textit{Case 2.}$ in $\#2$ or $\color{magenta} \clubsuit$ $ \boxed{\textbf{Extremal Chaining}}$ $\color{magenta} \clubsuit$ above, it's easily seen that any subchain of a larger-sized element is a representation of some integer.
So, by this logic, there exists an element of size $2$ with $a_r$ in its representation. Call this element $a + a_r$. Now consider an element (of size $2$) that attacks it using $b_r \in B$; that element must be in the form of
\[a_1 + a_2 = a + a_r + b_r \]First of all, by the Corollary in $\color{magenta} \clubsuit$ $ \boxed{\textbf{Extremal Chaining}}$ $\color{magenta} \clubsuit$, we know that $a_r + b_r \in A \cup B$. If this number is from $B$, then
\[ a_1 + a_2 = a + b \]for some $b \in B$. This will imply that $a_1 + a_2$ belongs to $A \cup B$, a contradiction. So $a_r + b_r \in A$. Repeating the same argument for some $b + b_r$ proves the Claim.
So, all members of $E = \{0,1,\ldots,n-1\} - S$ must be of unison color. We are done. $\blacksquare$ $\blacksquare$
We exclusively finish with solidifying $E$'s presence, or drawing conclusions from the vacuum of $A \cup B$.
$\color{blue} \rule{9.1cm}{2pt}$
$\color{blue} \clubsuit$ $\color{blue} \boxed{\textbf{Hard N: Two summands breaking extremal.}}$ $\color{blue} \clubsuit$
$\color{blue} \rule{9.1cm}{2pt}$
Suppose there exists some
\[ d \mid n, \: d \ne n \]so that
\[ S + d = S \]with the addition defined as usual. Then the minimal $d'$ which satisfies that equation will work for the problem.
Or else, then all the numbers from $\{0,1,\ldots,n-1\} - \{0\}$ has the same color, which evidently contradicts the problem statement.
$\color{blue} \rule{25cm}{0.2pt}$
$\color{blue} \spadesuit$ $\color{blue} \boxed{\textbf{Proof.}}$ $\color{blue} \spadesuit$
Noting that all elements of $E$ are attired with color $A$, we first prove that for every $d^* \in S$ of which
\[ S + d^* \ne S \]then $d^*$ has color $A$. (Strange notation, huh?)
If that holds, evidently there is another member $s' \in S$ so that $d^* + s' \in E$. If so, then $d^*$ can be chained down from $d^* + s'$, and that leaves nothing to proof.
From this working, it's natural to plug all members of $S$ and try its outcome on the equation $S + d^* = S$; if all members (except for $0$, of course) satisfies that equation, then all members of $S$ have color $A$, implying the $\color{blue} \text{Or else}$ conclusion.
The other outcome would be if $S + d' = S$ for some minimal $d' \mid n$. Then, we prove that if
\[ d \nmid x \Rightarrow x,x+d \ \text{have color} \ A\]implying that they have the same color.
Suppose there exists a rebellious $x \in S$ which does not have color $A$ --- so $x$ satisfies $S + x = S$. Combining this with $S + d = S$, we have
\[ S + kx + ld = S \]for every $k,l \in \mathbb{N}_0$, implying that if $g = \gcd{(x,d)}$ then
\[ S + g = S, \ g \mid d \mid n \]since we can construct $g \pmod d$ from adding $x$ multiple times, and adjust that to be equal to $g \pmod n$ by the appropriate summing of $d$. We are then truly done. $\blacksquare$ $\blacksquare$ $\blacksquare$
If this hasn't been apparent by now, this took a painstakingly grind-ful week (with breaks of doing other things, of course) to come up. Also, this is much better explained with pictures of circles shown below (which preludes each Section), so enjoy the relatively short Motivation!
(Most of the thought processes are also integrated in the Solution, and this exhibits the initial leads and the failures that lead up to the correct applications.)
$\color{green} \rule{25cm}{2pt}$
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.85]
\draw[thick,green] (0,0) circle(3); \\
\foreach \i/\j in {90/0,60/1,30/2,0/3,-30/4,-60/5,-90/6,-120/7,-150/8,-180/9,-210/10,-240/11} \node at (\i:2.6) {\j};
\foreach \i in {60,-30,-60,-150,-180,-240}
\draw[red,thick] ({2.6*cos(\i)+0.23},{2.6*sin(\i)+0.23})--({2.6*cos(\i)+0.23},{2.6*sin(\i)-0.23})--({2.6*cos(\i)-0.23},{2.6*sin(\i)-0.23})--({2.6*cos(\i)-0.23},{2.6*sin(\i)+0.23})--cycle;
\foreach \i in {3,-88,-120,-214,-244}
\draw[blue,thick,->] (60:2.2cm)--(\i:2.2cm);
\node[red] at (0,-3.5) {Fig 1.};
\end{tikzpicture}");[/asy][/asy]
$\color{red} \text{Sec 1. Fixing} \ S \ \text{and matching classes.}$ First I established that as $\textit{loose}$ as $S$'s recruitment process may be, at the end, it's much better if $S$'s elements are fixed in order to clearly determine which nodes are of equal colors with other nodes.
As I tried to fix $S = \{0,1,2\}$, $S = \{0,3\}$ and $S = \{0,1,4\}$ when $n = 6$, I quickly discovered that the first directly lead to a bigger advantage for the larger nodes, and the second one quickly establishes $d = 3$. The third one, however, presents a big problem: there's no clear direction as how to establish equal colors between some $d-$class.
Moreover, I also noticed that the $\textsf{size}$ of $S$ doesn't really matter --- it's equally easy to establish a contradiction from the likes of $S = \{0,1,3,4,5\}$, $S = \{0,2,3,4,5\}$ and $S = \{0,1\}$, as they all point out that all numbers from $1$ to $n-1$ have the same color.
After clearly dividing $\{0,1,\ldots,n-1\}$ to $S$ and not-$S$, it's evident that the $S$-members are $\textit{stuck}$ and not allowed to simply declare its color equal to other nodes, while if $y \not\in S$, there is a lot of liberty for it to use a member $s$ of $S$ so that $y-s$ has the same color with it. While this is only a restatement of the problem, it brings a clearer vision as to the roles of each number.
Now, fixing random $S$ such as $S = \{0,2,3,6,7,10\}$, I wanted to show that if $d = 1$, then all numbers except $0$ have the same color (a.k.a. connected with each other). The best idea out of them for me seemed to be to list all $\textit{classes}$ of the not-$S$ members: the node $1$ is of class-$11,10,7,6,3$ altogether at the same time. This representation of the chains might be strong on paper, but it obscures whether the classes are comparable to each other.
(Contrast this with the clear roles shown in Minimal Chaining.)
Other notable ideas include matching some member of $S$ to a not-$S$: here I discovered that if $s + S \ne S$, it's connected with some member of $S$ (all the more incentive to prove all the members of $S$ are connected) and some induction processes: if $S = \{0,3,6\}$, then by reducing $n = 12$ to $n = 4$, we can kinda be sure that the numbers $3,6,9$ have the same color.
$\color{green} \rule{25cm}{2pt}$
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.9]
\draw[thick,green] (0,0) circle(3);
\foreach \i in {0,1,...,13}
\node at ({90-\i*360/14}:2.6cm) {\i};
\foreach \i in {90,38.5714285714,-90}
\draw[red,thick] ({2.6*cos(\i)},{2.6*sin(\i)+0.33})--({2.6*cos(\i) + 0.33*cos(-30)},{2.6*sin(\i)+0.33*sin(-30)})--({2.6*cos(\i) + 0.33*cos(-150)},{2.6*sin(\i)+0.33*sin(-150)})--cycle;
\draw[blue!50!white,thick,<-] ({2.2*cos(87)},{2.2*sin(87)})--({2.2*cos(90-2*360/14)},{2.2*sin(90-2*360/14)});
\draw[blue!50!white,thick,->] ({2.2*cos(93)},{2.2*sin(93)})--({2.2*cos(90+2*360/14)},{2.2*sin(90+2*360/14)});
\draw[blue!50!white,thick,<->] ({2.2*cos(90)},{2.2*sin(90)})--({2.2*cos(90-7*360/14)},{2.2*sin(90-7*360/14)});
\draw[blue!50!white,thick,<-] ({2.2*cos(90+5*360/14)},{2.2*sin(90+5*360/14)})--({2.2*cos(90-2*360/14)},{2.2*sin(90-2*360/14)});
\draw[blue!50!white,thick,->] ({2.2*cos(90+7*360/14+3)},{2.2*sin(90+7*360/14+3)})--({2.2*cos(90-5*360/14)},{2.2*sin(90-5*360/14)});
\draw[blue,thick,->] ({2.2*cos(90+5*360/14+0.15)},{2.2*sin(90+5*360/14)-0.15})--({2.2*cos(90-2*360/14+0.15)},{2.2*sin(90-2*360/14)-0.15});
\node[red] at (0,-3.5) {Fig 2.};
\end{tikzpicture}");[/asy][/asy]
$\color{red} \text{Sec 2. Categorizing and dividing even further.}$ Now, assuming that the members of $S$ are quite diversified in factorization, I tried to pull out some conclusion from members of $S$ being attacked by some not-$S$. Then came the more sophisticated induction idea: set $n = 14$, and each $d$-wheel ($(0,7), (0,2,\ldots,12)$) has some faulty addition, then can't we pull out a contradiction from the varying colors available?
This gets more and more unprovable; but this idea brings forth the possibility of chaining from different wheels $\textit{explicitly}$; and as I hovered over my diagram for $S = \{0,2,7\}$ in Fig 2 (caption: all edges of length $2$ and $7$ are usable, except for the light blue edges emanating from the triangled-nodes) I noted the peculiar position of $9$ (note that $9 \rightarrow 2$ is usable.)
Operating on the assumption that $2 + 7 \not\in S$, it quickly dawned on me that $2$ and $7$ must have the same color. Now, if not all elements of $S$ have the same color, a new equation on set theory was naturally formulated:
\[ A + B \subset A \cup B \]and it dawned to me that even with separating the members of $S$, there could not be an easy way to establish equality (and all members may not be equally colored, after all).
By Cauchy-Davenport, we know that for some $A+B \ne A$ (or something similar) then $|A+B|$ is bounded below by $|A|+|B|-1$. Then, seeing as $A$ and $B$ are clearly disjoint, $A \cup B$ has $1$ more capacity than its theoretical minimum, and that brings more questions than answers.
Going back to my initial construction, I somehow noted that $7+7-2 = 12$, and the thought of extending $S = \{0,2,7\}$ to $\{0,2,5,7\}$ happened. Then, setting $A = \{2,7\}$ and $B = \{0,5\}$ brought a new chaos towards the equation --- as $S$'s roles can be divided even more in two with no blatant contradictions.
$\color{green} \rule{25cm}{2pt}$
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}
\node at (0,0) {2}; \node at (0,1.2) {0}; \node at (0,-1.2) {7}; \draw[green,thick,<-] (0.2,0.2)--(1,0.6); \draw[green,thick,<-] (0.2,-0.2)--(1,-0.6); \draw[green,thick,<-] (0.2,-1.2)--(1,-0.75);
\node at (1.5,0.6) {2+2}; \node at (1.5,-0.67) {2+7}; \draw[green,thick,<-] (2,0.8)--(2.8,1.2); \draw[green,thick,<-] (2,-0.6)--(2.8,-0.2);
\node at (3.45,1.2) {2+2+2}; \node at (3.45,-0.05) {7+2+2}; \draw[green,thick,<-] (4.2,1.2)--(5,0.8); \draw[green,thick,<-] (4.2,-0.2)--(5,-0.6);
\node at (5.95,0.6) {2+2+2+2}; \node at (5.95,-0.6) {2+2+2+7}; \draw[thick,red,->] (3.85,1)--(5.4,-0.3); \draw[thick,red,<-] (5.95,0.35)--(5.95,-0.35); \draw[green!70!white,thick,->] (6.7,0.34) arc (45:-45:0.48);
\begin{footnotesize}
\node[red] at (4.57,0.07) {5}; \node[red] at (6.18,0) {5}; \node[green] at (7.05,0) {7};
\begin{scope}[xshift = 0.65cm, yshift = -0.7cm]
\node at (0,-1) {1 =}; \node at (0,-1.33) {2 =}; \node at (0,-1.66) {3 =}; \node at (0,-1.99) {4 =}; \node at (1,-1) {2+2+2+7}; \node at (0.45,-1.33) {2}; \node at (0.83,-1.66) {5+5+5}; \node at (0.63,-1.99) {2+2};
\draw (1.75,-0.8)--(1.75,-2.2);
\node at (2.15,-1) {5 =}; \node at (2.15,-1.33) {6 =}; \node at (2.15,-1.66) {7 =}; \node at (2.15,-1.99) {8 =}; \node at (2.6,-1) {5}; \node at (2.98,-1.33) {2+2+2}; \node at (2.6,-1.66) {7}; \node at (3.15,-1.99) {2+2+2+2};
\draw (3.9,-0.8)--(3.9,-2.2);
\node at (4.48,-1) {9 =}; \node at (4.4,-1.33) {10 =}; \node at (4.4,-1.66) {11 =}; \node at (5.13,-1) {7+2}; \node at (5.13,-1.33) {5+5}; \node at (5.33,-1.66) {7+2+2};
\end{scope}
\end{footnotesize}
\draw[orange!23!white,dashed] (-0.2,-3)--(7.2,-3);
\node[red] at (3.5,-3.4) {Fig 3: $E_A$ stacked according to levels.};
\end{tikzpicture}");[/asy][/asy]
$\color{red} \text{Sec 3. Unexpected same color resolution.}$ While the Solution is slowly taking its form from this point onwards: here I settled the issue of $\textit{size}$ and its extremal-ity. As I further divided $\{0,1,\ldots,11\}$ into the ones shown in Fig 3, I tried to pull out conclusions based on the apparent size of the nodes, not its additive size.
Specifically, I let that if $e_a \in A+A$, then $e_a-b$ (for some $b$) must have a representation. This representation then cannot be of singular element, but I saw no resolution if that representation has a big size. Upon further reflection, the element $e_a-b$ cannot be a part of $B \cup E_B$; but it $\textbf{can}$ in fact be a big fish of $E_A$.
To mitigate this, I constructed the tree, and the idea came to draw out second-level elements from the top-levels by chaining it down to the first level. Then, I realized that what made this tree faulty is the existence of $2+2+2$ attacking the higher-leveled $2+2+2+7$ --- making $2+2+2+2$ (the other member of the fourth level) unable to attack $2+2+2+7$ using a $5$ arrow.
While this doesn't easily lead to the set theory argument, what made this seemed like the only way out was considering $E_A$ and $E_B$'s size (particularly if the $\text{gcd}$ of $B$'s elements is $d_B$, then $\dfrac{n}{d_B}$ seems to divide $|E_A|$) and pulling out almost no conclusions, since the collective nature of $E_A$ isn't quite trace-able as its individuals.
Notes.Note: the Set Theory Commercial Break can be done with members of higher size. Also, the large divisibility argument also made me consider what would happen if
\[ \dfrac{n}{d_B} \mid |E_A| \]and $E_A$ simply is a quite small set (this happens a lot when $|S| \geq \dfrac{n}{2}$, for example.) This would imply that no other set than $E_A = \{ \}$ would satisfy the equation.
$\color{green} \rule{25cm}{2pt}$
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.8]
\fill[orange!7!white] (0,0)--(84:3cm) arc (84:22:3cm)--cycle;
\begin{footnotesize}
\draw[thick,green] (0,0) circle (3);
\node at (90:2.6cm) {0}; \node at (78:2.6cm) {1}; \node at (30:2.6cm) {$d-1$}; \node at (18:2.6cm) {$d$};
\end{footnotesize}
\draw[green,thick] (0,0)--(96:3cm); \draw[green,thick](0,0)--(22:3cm); \draw[red,thick] (0,0)--(84:3cm);
\node[red] at (0,-3.4) {Fig 4.};
\end{tikzpicture}");[/asy][/asy]
$\color{red} \text{Sec 4. Basics + the inconspicuous red flag.}$ After all this hard work establishing $E$'s elements are equally attired, it seems that all members of $S$ are also connected to some of $E$'s members. However, this flashed back the equation of $S + d = S$ to mind.
Here I re-examined the initial train of thought when $d \ne 1$: isn't this quite easy to establish at the first place? It turns out that except $S + d = S$ happens, then almost all members of the $d$-circle $\{0,d,2d,\ldots, kd = n-d\}$ must have the same color.
So, instead of considering the $\text{gcd}$ elements of $B$ (when we have $E = E_A$), I considered the common divisor of elements of $S - A$. This was more profitable in my mind as the elements of $S$ which must be in $A$ are easily verified to be there (as they are connected to some element of $E$) while the others present a problem --- they may in fact camouflage as members of $A$ or $B$.
To remove ambiguity, assuming they do exist (or else, $\color{blue} \text{Or else}$ happens, which is prohibited by the problem statement) then there must be a most extreme summand $d$ so that $S + d = S$.
Then, if there is some non-compliant element of $\{0,1,\ldots,n-1\} - \{0,d,\ldots,n-d\}$, then that element (say it is $x$) also brings an added calamity on the set-summation equation. By USAMO 2001-5 arguments, the minimal then can be lowered --- and we are finally done.
Notes.An example with $\gcd{(S,n)} = 1$ but $d \ne 1$ would be $S = \{0,1,3,4\}$ with $1,4,2,5$ having color $A$, and $0,3$ having undetermined colors.
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \blacksquare \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]