La coloración de un tablero de ajedrez

Question

¿Cómo puedo demostrar que puedo, el color es un $2n\times\binom{2n}{2}$ tablero de ajedrez, con $n$ diferentes colores, de tal manera que no hay $4$ unidad separada de cuadrados del mismo color, los centros de los cuales son los vértices de un rectángulo con lados paralelos a los lados de la junta?

Answer 1

No es una solución, sino un comienzo. Vamos a la $2n$ el rumbo de las filas y el ${2n \choose 2}$ el rumbo de las columnas. Parece obvio que colocar dos cuadrados de un color determinado en cada columna, y cada columna es un par diferente de filas. Sólo hay suficientes pares de filas para ello. Si podemos lograr esto (es decir, si un color no en otra manera) que se hacen. Un boceto rápido muestra que funciona bien para $n=2$. El problema viene por $n=3$. Sería natural para el paso a través de los colores con columnas como $112233, 122331, 223311, \ldots 311223, 123123, 312312, 213213$ pero surge un problema con $1x1xxx$ ya que no se puede llenar con $2$'s y $3$'s con una única brecha cada uno. Esto puede ser resuelto mediante la mezcla correctamente, dando a $$123313212321123\\213221313132231\\131233221132312\\212132331213123\\331312122213231\\322121133321312$$ pero no he encontrado una buena fórmula o la inducción para demostrar que siempre funciona.

Answer 2

Como de costumbre, $[m]=\{1,2,\dots,m\}$ por cada $m\in\Bbb Z^+$, y para cualquier conjunto $S$, $[S]^2$ es el conjunto de pares no ordenados de elementos de $S$. Para un entero positivo $m$ y enteros $a$ $b$ definir $a\oplus_m b$ a de ser la única $k\in[m]$ tal que $a+b\equiv k\pmod m$.

Ahora fijar un entero positivo $n$, y deje $m=2n-1$. Para $i,k\in\{0,\dots,m\}$ deje $a_{i,k}=i\oplus_m k$, y vamos a

$$b_{i,k}=\begin{cases} 0,&\text{if }i=k\\ a_{i,k},&\text{if }i\ne m\ne k\\ a_{i,i},&\text{if }i<k=m\\ a_{k,k},&\text{if }k<i=m \end{casos}$$

No es difícil comprobar que $a_{i,m}=a_{i,1}$ y, a continuación, que $\{b_{i,0},\dots,b_{i,m}\}=\{0,\dots,m\}$$i=0,\dots,m$. Por otra parte, es claro que $b_{i,k}=b_{k,i}$$i,k\in\{0,\dots,m\}$. Para $c\in[m]$ vamos

$$P_c=\big\{\{i,k\}\in[m]^2:b_{i,k}=c\big\}\;,$$

y deje $\mathscr{P}=\{P_c:c\in[m]\}$. Cada una de las $P_c\in\mathscr{P}$ es una partición de a $[2n]$ a $n$ desordenada pares, y $\bigcup\mathscr{P}=[2n]^2$. Para cada una de las $c\in[m]$ deje $P_c=\big\{\{r_{c,k},s_{c,k}\}:k\in[n]\big\}$.

Índice de las columnas de la junta por $[m]\times[n]$, partición de las celdas de la columna $\langle c,q\rangle$ según $P_c$, y para $k\in[n]$ color de las celdas en las filas de la $r_{c,k}$ $s_{c,k}$ color $k\oplus_nq$.

Supongamos que $r,s\in[n]$, $\langle c,q\rangle,\langle d,p\rangle\in[m]\times[n]$, $r\ne s$, y las células en las intersecciones de estas filas $r$ $s$ de columnas $\langle c,q\rangle$ $\langle d,p\rangle$ son todos del mismo color. A continuación,$\{r,s\}\in P_c\cap P_d$, por lo que $c=d$, $\{r,s\}=\{r_{c,k},s_{c,k}\}$ para algunos $k\in[n]$, $k\oplus_nq=k\oplus_np$, y $q=p$, por lo que el $\langle c,q\rangle=\langle d,p\rangle$. Por lo tanto, no rectángulo con lados paralelos a los lados de la junta directiva tiene las cuatro esquinas del mismo color.

Answer 3

EDIT: Esto no es una respuesta; lo he probado.

Como siga este argumento, puede ayudar a mantener el caso en $n=3$ en mente. Seguir leyendo un rato antes de colorantes y matrices entran en juego.

Considere la posibilidad de la $n$ ejes en $\mathbb{R}^n$. Dar el estándar de los vectores de la base nombres de $e_i$. Coloque un vértice en $\pm e_i$. Conecte estos vértices con los bordes en todos los $\binom{2n}{2}$ formas posibles. Algunos de estos bordes ($n$ de ellos) son los segmentos a lo largo de los ejes, y vamos a recoger estos bordes en un ordenado conjunto de $A=\{A_1,\ldots,A_n\}$. El resto en forma de algún tipo de dimensiones superiores generalización de un octaedro. Pongamos nombre a estos bordes $\pm e_i\pm e_j,i< j$. No hay literal de la suma o la resta. Por ejemplo, para $n=2$ tenemos $e_1+e_2,e_1-e_2,-e_1+e_2,-e_1-e_2$. Debe $e_2-e_1$ surgir, que significa lo mismo que $-e_1+e_2$.

Para $k=2,3,\ldots n$, consideran que la ordenó subconjunto de estos bordes $S=\{e_1-e_2,e_2-e_3,\ldots,e_n-e_{1}\}$. No hay dos bordes en $S$ son adyacentes desde cada vértice de la "octohedron" está presente una vez.

Ahora bien, si sólo hubo una transformación ortogonal $R$ con el fin de $2(n-1)$ tal de que las órbitas de $S$ cubierto todos los bordes, yo podría continuar. Es fácil encontrar ese $R$$n=2,3$; podemos visualizar $R$ como una rotación. Pero para mayor $n$, estoy a falta de encontrar una generalización. Si hemos tenido una $R$, entonces vamos a tener particionada la $\binom{2n}{2}$ bordes en $2(n-1)+1=2n-1$ bloques de tamaño $n$; es decir $A$ e las $R^kS$. Dentro de cada bloque, no hay dos bordes adyacentes.

Ahora consideremos la matriz $$ \begin{array}{ccccc} +e_1&+e_1&+e_1\cdots\\ -e_1&-e_1&-e_1\cdots\\ +e_2&+e_2&+e_2\cdots\\ -e_2&-e_2&-e_2\cdots\\ \vdots&\vdots&\vdots\\ +e_n&+e_n&+e_n\cdots\\ -e_n&-e_n&-e_n\cdots\\ \end{array}$$ con $\binom{2n}{2}$ columnas. Identificar cada columna con una arista del grafo. Cada arista del grafo es en uno de los pedidos de los bloques que hemos creado, así que tenga en cuenta que de esta manera cada columna cae en uno de esos bloques.

En cada columna, localizar los vértices que corresponden a la columna asociada del borde y el color de ellas la primera en color, digamos rojo. No puede ser un rectángulo de color rojo, ya que implicaría tenemos dos columnas correspondientes a la misma orilla.

$$\begin{array}{ccccc} {\color{red}{+e_1}}&{\color{red}{+e_1}}&{\color{red}{+e_1}}\cdots\\ -e_1&-e_1&-e_1\cdots\\ +e_2&+e_2&+e_2\cdots\\ {\color{red}{-e_2}}&-e_2&-e_2\cdots\\ \vdots&\vdots&\vdots\\ +e_n&+e_n&+e_n\cdots\\ -e_n&-e_n&-e_n\cdots\\ \end{array}$$

En cada columna, busque en la asociada y bloque de iteración a la siguiente arista. El Color de los vértices del segundo color, el azul. De nuevo, no habrá rectángulo azul, ya que nuestros bloques son disjuntas.

$$\begin{array}{ccc} {\color{red}{+e_1}}&{\color{red}{+e_1}}&{\color{red}{+e_1}}\cdots\\ -e_1&-e_1&-e_1\cdots\\ {\color{blue}{+e_2}}&{\color{blue}{+e_2}}&{\color{blue}{+e_2}}\cdots\\ {\color{red}{-e_2}}&-e_2&-e_2\cdots\\ +e_3&+e_3&+e_3\cdots\\ {\color{blue}{-e_3}}&{\color{red}{-e_3}}&-e_3\cdots\\ \vdots&\vdots&\vdots\\ +e_n&+e_n&+e_n\cdots\\ -e_n&-e_n&-e_n\cdots\\ \end{array}$$

Continuar ciclismo de esta manera a través de todos los colores.

Answer 4

Este es el Corolario 3.7 (aparece en la parte inferior de la página 18 del proyecto de Ley Gasarch et al papel de Rectángulo Libre de Coloraciones de las Mallas.

El papel está aquí: http://www.cs.umd.edu/~gasarch/papers/cuadrícula.pdf

Hay un montón más resultados en allí, si usted está interesado en ellos.

Buena suerte!