How find the "how many good dyeing" method
$A_{1},A_{2},\cdots,A_{2013}$ are $2013$ different points placed on the circumference of a circle. Each point is dyed one of three colors: red, blue and green. We call a dyeing method good, if for any two points that have the same color, the arc which have these points as the endpoints contain an even number of points which do not have this same color. How many good dyeing methods are there?
Sorry, my English is not very good, and this problem is original problem in Chinese:
Translation: $A_{1},A_{2},\cdots,A_{2013}$ are 2013 different points placed on the circumference of a circle. Each point is colored one of three colors: red, blue and green. We call a coloring method good, if for any two points that have the same color, the arc which have these points as the endpoints contain an even number of points which do not have this same color. How many good coloring methods are there?
for example:
the fisrt picture have 13 point,That Subject the condition
and second picture have 8 point,subject the condtion too
and the third picture have 11 point, and subject the condtion too
and the four picture have 10 point,and can't subject the condtion,because in short arc blue+blue+green =3 point not even number
By this :this problem is from olympic Problem (2013,7,20,china ) ,and is very interesting with this mathematics olympic problem, It is sad this problem No one solve it, So I hope someone can help
Answer: There are $3$ monochromatic colorings and $2^n-2$ colorings that use 3 colors; the total number of colorings in $2^n+1$.
It's easy to see that there are three colorings that use only one color and there are no colorings that use exactly two colors. We compute the number of colorings that use exactly 3 colors.
Let $n=2013$ be the number of points; we will use that $n$ is odd. Let us say that a coloring $c$ is valid if it satisfies the condition of the problem; let us say that a coloring $d$ is proper if adjacent points have different colors. For convenience, we denote $A_{i-n} = A_i$ for every $i\in\{1,\dots, n\}$.
Overview (informal).
We are going to prove that there is a one-to-one correspondence between valid colorings $c$ and proper colorings $d$ (we will use that $n$ is odd). Then we will show that the number of proper colorings $d$ is $2^n-2$.
Given a proper coloring $d$, we define a valid coloring $c$ as follows $c(i)$ is the color other than $d(i)$ and $d(i+1)$. Color $c(i)$ is well-defined since $d(i)$ and $d(i+1)$ have different colors and thus there is one color other than $d(i)$ and $d(i+1)$. Here is an example:
\begin{array}[llllllll] \ &A_1 & A_2 & A_3 & A_4 & A_5 & A_6 & A_7 \\ \hline \mathbf{\text{coloring } d} & R & G & R & G & B & G & B \\ \mathbf{\text{coloring } c} & B & B & B & R & R & R & G \\ \hline \end{array}
Note that $c$ is a valid coloring: consider two points $A_i$ and $A_j$ of the same color $a = c(i) = c(j)$ such that there are no points of the same color $a$ between them. Let us say that $c(i) = R$. Then $\{d(i), d(i+1)\} = \{d(j), d(j+1)\} = \{G, B\}$. For every $k$ between $i$ and $j$: $\{d(k), d(k+1)\} \neq \{G, B\}$ (as otherwise, $c(k) = R$ which contradicts to the fact that all points between $i$ and $j$ are not $R$). This means that points $c(i+1), \dots, c(j)$ have pattern:
not Red, Red, not Red, Red, not Red, Red, ..., not Red
Therefore, $i-j$ is odd. Therefore, $c$ is a valid coloring. We will show that the correspondence is one-to-one.
Formal proof.
Consider a coloring $c$ (that uses all three colors); $c(i)$ is the color of point $i$; $c(i-n) = c(i)$. Let $p_a(i)$ be the index of the previous point of color $a$: $$p_a(i) = \max \{j: j < i \text{ and } c(j) = a\}.$$ Note that $p_a(i)$ is well-defined since the coloring uses all three colors. Let $q(i) = p_{c(i)} (i)$ (it is possible that $q(i) = i - n$).
Note that the coloring is valid if and only if $i-q(i)$ is odd for every $i\in \{1,\dots, n\}$. Let us say that a color $a$ is admissible at position $i$ if $p_a(i) - i$ is odd. Then the coloring $c$ is valid if and only if $c(i)$ is admissible at position $i$ for every $i$. Let $A(i)$ be the set of colors admissible at position $i$. We will encode $A(i)$ by a bit string $B(i)$: the first bit indicates whether red is in $A(i)$, the second whether green is in $A(i)$, and the third whether blue is in $A(i)$. E.g. $011$ encodes set $\{\text{green}, \text{blue}\}$.
Note that if $c$ is a valid coloring then $c(i) \in A(i)$. Moreover, $c(i) \in A(i+1)$ since $(i+1) - p_{c(i)}(i+1) = (i+1) - i = 1$ is odd. On the other hand, if $a \neq c(i)$ then $p_a(i) = p_a(i+1)$ and thus $a$ is either in $A(i)$ or $A(i+1)$ but not both of them. This means that
- if $B(i) = 111$ then $B(i+1) \in \{100, 010, 001\}$,
- if $B(i) \in \{100, 010, 001\}$ then $B(i+1) =111$,
- if $B(i) = 110$ then $B(i+1) \in \{101, 011\}$.
Observe that if $B(i) = 111$ then $B(i+2) = 111$ (by 1 and 2). Consequently, $B(i) = 111$ for every $i$ (since $n$ is odd), which contradict to item 1. Thus $B(i) \neq 111$ for every $i$. Also $B(i) \notin \{100, 010, 001\}$ as otherwise, we would have $B(i+1) =111$.
We conclude that $B(i) = \{101, 011, 110\}$. That is, $|A(i)| = 2$ for every $i$. Let $d(i)$ be the color that is not in $A(i)$. From item 3, we get that $d(i) \neq d(i+1)$. We conclude that every valid coloring $c$ defines a coloring $d(i)$ that satisfies $d(i) \neq d(i+1)$. That is, $d$ is a proper coloring of the cycle of length $n$.
We show now that every proper coloring $d'$ (with $d'(i) \neq d(i+1)$) corresponds to a valid coloring $c$ (we outlined the proof in the overview). Consider such a coloring $d'$. It defines sets $A'(i)$ and strings $B'(i)$ satisfying item 3. Define $c(i) = A'(i) \cap A'(i+1)$. Consider two consecutive vertices $i$ and $j$ of color $a$ (that is, $i = p_a(j)$). Note that $a\in A'(i)$ and $a\in A'(j)$ and $a$ belongs to every other set $A'(k)$ for $k\in \{i, \dots, j\}$. Therefore, $|i-j|$ is odd. Thus $c$ is a valid coloring. (Note that $d$ uses $3$ colors since $d$ is odd, and thus $c$ also uses 3 colors).
We established a one-to-one correspondence between valid colorings $c$ and proper colorings $d$. Now it is easy to see that the number of colorings $d$ is $2^n-2$ (see below).
How to compute the number of colorings $d$.
Let $A_n$ be the number of proper 3-colorings $d$ of a line (i.e. colorings with $d(i) \neq d(i+1)$) such that $d(1) = d(n)$, and $B_n$ be the number of proper 3-colorings of a line with $d(1) \neq d(n)$. We write, \begin{align*} A_{n+2} &= 2 A_n + B_n\\ B_{n+2} &= 2A_n + 3B_n \end{align*} We solve this recurrence and get $A_n = 2^{n-1}+2$ and $B_n = 2^n - 2$. Now we observe that he number of proper colorings $d$ of a cycle equals $B_n$.