Un bonito y duro a la coloración problema

Question

Esta pregunta es una generalización de un problema apareció recientemente en un italiano competencia de matemáticas.

$A$ $B$ son dos coprime enteros, tanto mayor que $2$. Un no constantes de la coloración $$ c:I=\{1,2,3,\ldots,n\}\mapsto \{0,1\}$$ ha la siguientes propiedades:

• si $u,v\in I$ y $|u-v|=A$, $c(u)=c(v)$;
• si $u,v\in I$ y $|u-v|=B$, $c(u)=c(v)$.

¿Cuál es el máximo valor de $n$, como una función de la $A$$B$?

En el problema original, $A=11$$B=16$. Si asumimos que el $c(a)=1$ (vamos que decir que $a$ es de color negro), a continuación, $a+11,a+22,a+33,\ldots$ son de color negro, también. Suponiendo que $n>22$, $a+6,a+17,a+28,\ldots$ son de color negro, también. Podemos continuar de esta manera hasta que un número en el rango de $a,\ldots,a+10$ todavía está en blanco, entonces deducir el valor máximo de $n$.

También podemos notar que si $AB_1-BA_1=1$,$1\leq A_1<A$$1\leq B_1<B$, e $k,k+1$ son los primeros números con diferentes colores, debemos tener $n<k+AB_1$. Así que la respuesta a la generalización de arriba debe ser dependiente de Bézout de la identidad y de la longitud del algoritmo de Euclides para $\gcd(A,B)=1$. Me pregunto cómo.

También podemos notar que si $n$ es máxima, $c(A)$ $c(B)$ tienen que ser diferentes (por lo que puede suponer $c(\min(A,B))=1$ WLOG), de lo contrario podemos introducir un elemento $0$ y darle el mismo color de $A$, a continuación, volver a indexar los elementos de $I$, contradiciendo la maximality de $n$. Que conduce a:

$$ \max n\leq A+B-1.$$

Answer 1

Suponga $2\leq A<B$. A continuación, $B=qA+r$ con $q\geq1$, $\>1\leq r\leq A-1$, y $r$ primer a $A$.

Imaginar un "resumen" regular $A$-gon con conjunto de vértices $V\sim{\mathbb Z}/A$. Si sacamos las $A$ acordes $\{k,k+r\}$ obtenemos un cíclica gráfico de $\Gamma$. La omisión de un borde de $\Gamma$ deja un grafo conexo $\Gamma'$, pero si omitimos $\geq2$ bordes de $\Gamma$ el gráfico resultante en $V$ no está conectado.

El conjunto $[n]:=\{1,2,\ldots, n\}$ se divide en $A$ resto de clases del modulo $A$. Todos los miembros de la misma clase son de color con el mismo color; por lo tanto, cada clase tiene su color. Algunas de estas clases están relacionados por una $B$-salto y por lo tanto se le asigna el mismo color. La posible $B$-saltos $$1\to1+B, \quad 2\to 2+B, \quad \ldots, \quad n-B\to n\ .$$ El primer $A$ de estos saltos de plomo a los diferentes bordes de $\Gamma$.

Si $n-B\leq A-2$ o $n\leq A+B-2$, luego que no todas las clases del modulo $A$ están conectados por $B$-saltos, por lo que no constante para colorear de $[n]$ de la deseada tipo es posible. Si, sin embargo, $n-B\geq A-1$ o$n\geq A+B-1$, $\geq A-1$ diferentes acordes en $\Gamma$ se dio cuenta, que implica entonces que todo el resto de las clases del modulo $A$ va a obtener el mismo color.

Answer 2

Sólo algunas reflexiones para la dirección de más respuestas.

Vamos que decir que un color es maximal si $n$ es máxima. Como se indica en la pregunta, en un máximo de coloración $c$, $A$ y $B$ no pueden tener el mismo color, de lo contrario podemos definir $c'$ $\{1,\ldots,n+1\}$ tal que $c'(1)=c(A)=c(B)$ $c'(m)=c(m-1)$ cualquier $m\geq 1$, que conduce a una válida la coloración y contradiciendo el maximality de $n$. Así, hasta el cambio de colores, podemos asumir que cualquier máxima coloración cumple $c(A)=1$$c(B)=0$, lo $n<A+B$ como ya se ha dicho. También podemos asumir $A<B$ sin pérdida de generalidad. $c(A)=1$ en realidad le da al conjunto la coloración: $1=c(2A)=c(3A)=\ldots$ debe sostener, y asumiendo la $k=\left\lceil\frac{B}{A}\right\rceil$, $1=c(kA-B)$ debe poseer demasiado, por lo $1=c((k+1)A-B)=c((k+2)A-B)=\ldots$. Suponiendo que $j$ es el menor entero tal que $(k+j)A-B>B$, es decir,$(k+j)A>2B$, debemos tener $c((k+j)A-2B)=1$ y así sucesivamente. Podemos continuar hasta que hay un elemento en el intervalo de $[1,A]$ que aún tiene color $0$. Después de eso, el procedimiento da color a $1$ tanto $B$$B-A\in[1,A]$, que conduce a una constante de la coloración. Por lo $n$ está dado por la longitud máxima que nos permite, no para dar color a $1$ $B$o $B-A$.

Aquí es lo que sucede con $A=11,B=16$: $$\begin{array}{l}A=11\mapsto 22 \\ 6\mapsto 17\\ 1\mapsto 12\mapsto 23\\ 7\mapsto 18\\ 2\mapsto 13\mapsto 24\\ 8\mapsto 19\\ 3\mapsto 14\mapsto 25\\ 9\mapsto 20\\ 4\mapsto 15\mapsto \color{red}{26}\\ \color{red}{10\mapsto 21}\\ \color{red}{5\mapsto 16=B}\end{array}$$ si permitimos $26=A+B-1$ tener color $1$, entonces cualquier número en el intervalo de $[1,A]$ color $1$, e $B$ color $1$. Así tenemos que la longitud máxima para$A=11,B=16$$\color{red}{n=25}$, y el siguiente es de un máximo de coloración: $$ c^{-1}(1) = \{1,2,3,4,6,7,8,9,11,12,13,14,15,17,18,19,20,22,23,24,25\}, $$ $$ c^{-1}(0) = \{5,10,16,21\}. $$