Respuesta: Hay $3$ monocromática colorantes y $2^n-2$ colorantes que uso 3 colores; el número total de colorantes en $2^n+1$.
Es fácil ver que hay tres colorantes que uso un solo color y no hay colorantes que usar exactamente dos colores. Calculamos el número de colores que usan exactamente 3 colores.
Deje $n=2013$ el número de puntos, vamos a usar ese $n$ es impar. Digamos que es un colorante $c$ es válido si se cumple la condición de que el problema; digamos que un colorante $d$ es adecuada si los puntos adyacentes tengan colores distintos. Para mayor comodidad, se denotan $A_{i-n} = A_i$ por cada $i\in\{1,\dots, n\}$.
Descripción general (informal).
Vamos a demostrar que existe una correspondencia uno a uno entre válido colorantes $c$ adecuada y colorantes $d$ (vamos a usar ese $n$ es impar). A continuación, vamos a mostrar que el número apropiado de colorantes $d$$2^n-2$.
Dada una adecuada coloración $d$, podemos definir un válido para colorear $c$ siguiente $c(i)$ es el color de $d(i)$$d(i+1)$. Color $c(i)$ está bien definido desde $d(i)$ $d(i+1)$ tienen colores diferentes y por lo tanto no es de un color distinto a $d(i)$$d(i+1)$. He aquí un ejemplo:
\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}
Tenga en cuenta que $c$ es válido para colorear: considere dos puntos de $A_i$ $A_j$ respecto del mismo color $a = c(i) = c(j)$ tal de que no hay puntos del mismo color $a$ entre ellos. Digamos que $c(i) = R$. A continuación,$\{d(i), d(i+1)\} = \{d(j), d(j+1)\} = \{G, B\}$. Para cada $k$ $i$ y $j$: $\{d(k), d(k+1)\} \neq \{G, B\}$ (ya que de lo contrario, $c(k) = R$, lo que contradice el hecho de que todos los puntos entre el $i$ $j$ no $R$). Esto significa que los puntos de $c(i+1), \dots, c(j)$ han patrón:
not Red, Red, not Red, Red, not Red, Red, ..., not Red
Por lo tanto, $i-j$ es impar. Por lo tanto, $c$ es válido para colorear. Vamos a mostrar que la correspondencia uno-a-uno.
La prueba Formal.
Considere la posibilidad de un colorante $c$ (que utiliza los tres colores); $c(i)$ es el color del punto $i$; $c(i-n) = c(i)$. Deje $p_a(i)$ ser el índice en el punto anterior, de color $a$:
$$p_a(i) = \max \{j: j < i \text{ and } c(j) = a\}.$$
Tenga en cuenta que $p_a(i)$ está bien definido desde el colorante utiliza los tres colores. Deje $q(i) = p_{c(i)} (i)$ (es posible que $q(i) = i - n$).
Tenga en cuenta que la coloración es válido si y sólo si $i-q(i)$ es impar para cada $i\in \{1,\dots, n\}$. Digamos que es un color $a$ es admisible en la posición $i$ si $p_a(i) - i$ es impar. A continuación, el colorante $c$ es válido si y sólo si $c(i)$ es admisible en la posición $i$ por cada $i$. Deje $A(i)$ el conjunto de colores admisible en la posición $i$. Vamos a codificar $A(i)$ por una cadena de bits $B(i)$: el primer bit indica si el rojo es en $A(i)$, el segundo si el verde es en $A(i)$, y la tercera si azul es en $A(i)$. E. g. $011$ codifica set $\{\text{green}, \text{blue}\}$.
Tenga en cuenta que si $c$ es válido para colorear a continuación,$c(i) \in A(i)$. Por otra parte, $c(i) \in A(i+1)$ desde $(i+1) - p_{c(i)}(i+1) = (i+1) - i = 1$ es impar. Por otro lado, si $a \neq c(i)$ $p_a(i) = p_a(i+1)$ e lo $a$ es de $A(i)$ o $A(i+1)$, pero no ambos. Esto significa que
- si $B(i) = 111$$B(i+1) \in \{100, 010, 001\}$,
- si $B(i) \in \{100, 010, 001\}$$B(i+1) =111$,
- si $B(i) = 110$$B(i+1) \in \{101, 011\}$.
Observar que si $B(i) = 111$ $B(i+2) = 111$ (1 y 2). En consecuencia, $B(i) = 111$ por cada $i$ (desde $n$ es impar), lo que contradice el punto 1. Por lo tanto $B(i) \neq 111$ por cada $i$. También se $B(i) \notin \{100, 010, 001\}$ ya que de lo contrario, tendríamos $B(i+1) =111$.
Llegamos a la conclusión de que $B(i) = \{101, 011, 110\}$. Es decir, $|A(i)| = 2$ por cada $i$. Deje $d(i)$ ser el color que no está en $A(i)$. Desde el punto 3, obtenemos que $d(i) \neq d(i+1)$. Llegamos a la conclusión de que cada válido para colorear $c$ define una coloración $d(i)$ que satisface $d(i) \neq d(i+1)$. Es decir, $d$ es apropiado para colorear del ciclo de longitud $n$.
Mostramos ahora que cada apropiado para colorear $d'$ ( $d'(i) \neq d(i+1)$ ) corresponde a un válido para colorear $c$ (se describe la prueba en la introducción). Considere la posibilidad de un colorante $d'$. Se define conjuntos de $A'(i)$ y las cadenas de $B'(i)$ satisfactorio el punto 3. Definir $c(i) = A'(i) \cap A'(i+1)$. Considere dos vértices consecutivos $i$ $j$ color $a$ (es decir, $i = p_a(j)$). Tenga en cuenta que $a\in A'(i)$ $a\in A'(j)$ $a$ pertenece a todos los otros $A'(k)$$k\in \{i, \dots, j\}$. Por lo tanto, $|i-j|$ es impar. Por lo tanto $c$ es válido para colorear. (Tenga en cuenta que $d$ usa $3$ colores desde $d$ es impar, y por lo tanto $c$ también utiliza 3 colores).
Hemos establecido una correspondencia uno a uno entre válido colorantes $c$ adecuada y colorantes $d$. Ahora es fácil ver que el número de colorantes $d$ $2^n-2$ (ver abajo).
Cómo calcular el número de colorantes $d$.
Deje $A_n$ el número de adecuado 3-colorantes $d$ de una línea (es decir, los colorantes con $d(i) \neq d(i+1)$) tal que $d(1) = d(n)$, e $B_n$ el número de adecuado 3-el color de una línea con $d(1) \neq d(n)$. Escribimos,
\begin{align*}
A_{n+2} &= 2 A_n + B_n\\
B_{n+2} &= 2A_n + 3B_n
\end{align*}
Podemos resolver este recurrencia y obtenga $A_n = 2^{n-1}+2$$B_n = 2^n - 2$. Ahora podemos observar que el número apropiado de colorantes $d$ de un ciclo es igual a $B_n$.
