¿De cuántas maneras puedes colorear los vértices de una cuadrícula con 4 colores para que todos los vértices de la unidad cuadrada sean de un color diferente?

Question

¿De cuántas maneras se pueden colorear los vértices de un $(n\times n)$ -cuadrado formando un $(n+1)$ -grid con $4$ colores para que todos los vértices del cuadrado de la unidad sean de un color diferente?

Precisiones:

$(n\times n)$ -cuadrado : cuadrado cuya longitud de arista es $n$ .

$(n+1)$ -grid : rejilla cuadrada que contiene $(n+1)$ vértices por lado, y compuesto por $n^2$ cuadrados unitarios de dimensión $(1\times 1)$ .

Estos son algunos ejemplos para $n=1,2,3$

Mi intento :

He publicado una pregunta similar aquí Traté de hacer lo mismo (Porque la respuesta es así también ( $24\times (2^{n}-1)$ )) pero no respondió.

¿Alguna pista?

Answer 1

Consideremos una cuadrícula rectangular que contiene $m$ cuadrados en cada columna y $n$ cuadrados en cada fila. Rotula las filas de cuadrados con los índices $1$ , $2$ , ..., $m$ y las filas de vértices por los índices $0$ , $1$ , ..., $m$ y hacer lo mismo con las columnas. Supongamos que los vértices de la cuadrícula se han coloreado de tal manera que cada uno de los $mn$ cuadrados contiene un vértice de cada color.

Supongamos ahora que se añade una nueva fila de casillas a la cuadrícula. ¿Puede extenderse la coloración anterior a la última fila de vértices (fila $m+1$ )? Si es así, ¿de cuántas maneras? La respuesta a la primera pregunta es que sí. Esto es así porque podemos colorear la fila $m+1$ de la misma manera que coloreamos la fila $m-1$ . Para responder a la segunda pregunta, observe que, una vez decidido el color de cualquier vértice de la fila, se determinan los colores de todos los vértices restantes de la fila, suponiendo que sea posible una coloración. (Se colorean sucesivamente los vecinos de los vértices previamente coloreados hasta que se colorea toda la fila. Cada vértice que se colorea es el cuarto miembro de un cuadrado en el que ya se han coloreado tres vértices. O bien el cuarto color será único o dos de los tres colores ya utilizados serán el mismo, haciendo que la coloración sea insostenible). Como el primer vértice puede ser coloreado de dos maneras, concluimos que la fila $m+1$ tiene al menos una coloración y como máximo dos coloraciones.

Para determinar si el número de coloraciones es uno o dos, observe que si la coloración de la fila $m$ utiliza tres o cuatro colores, que en algún momento de la fila tendremos $$ m:\ \ldots abc\ldots, $$ donde $a$ , $b$ y $c$ son de diferentes colores. Los colores en las posiciones correspondientes en la fila $m+1$ son entonces forzados, $$ \begin{aligned} m:&\ \ldots abc\ldots\\ m+1:&\ \ldots cda\ldots, \end{aligned} $$ donde $d\notin\{a,b,c\}$ . De hecho, los colores en las posiciones correspondientes en la fila $m-1$ son forzados de la misma manera, y las filas $m-1$ y $m+1$ se colorean de forma idéntica. Así que en este caso hay una coloración de la fila $m+1$ . Además, el número de colores utilizados en la columna $n$ no se modificará por la adición de la fila $m+1$ .

Si la fila $m$ utiliza sólo dos colores, entonces son posibles dos coloraciones para la fila $m+1$ , $$ \begin{aligned} m:&\ abababa\ldots & m:&\ abababa\ldots\\ m+1:&\ cdcdcdc\ldots & m+1:&\ dcdcdcd\ldots. \end{aligned} $$ El número de colores utilizados en la columna $n$ puede ser modificada por la adición de la fila $m+1$ .

Observe que si una fila utiliza sólo dos colores, entonces todas las filas anteriores y posteriores sólo utilizan dos colores; si una fila utiliza tres o más colores, entonces todas las filas anteriores y posteriores utilizan tres o más colores. Es evidente que consideraciones similares se aplican a las columnas.

Ahora estamos en condiciones de escribir un sistema de recurrencias para el número de coloraciones de un $m\times n$ de la rejilla. Definir $$ \begin{aligned} Q_{m,n}&=\text{num. colorings with two colors in row $ m $, two colors in column $ n $,}\\ R_{m,n}&=\text{num. colorings with two colors in row $ m $, three colors in column $ n $,}\\ S_{m,n}&=\text{num. colorings with three colors in row $ m $, two colors in column $ n $,}\\ T_{m,n}&=\text{num. colorings with three colors in row $ m $, three colors in column $ n $.} \end{aligned} $$ Entonces $$ \begin{aligned} \begin{bmatrix}Q_{1,1} & R_{1,1}\\ S_{1,1} & T_{1,1}\end{bmatrix}&=24\cdot\begin{bmatrix}1 & 0\\ 0 & 0\end{bmatrix}\\ \begin{bmatrix}Q_{m,n} & R_{m,n}\\ S_{m,n} & T_{m,n}\end{bmatrix}&=\begin{bmatrix}Q_{m-1,n} & Q_{m-1,n}+2R_{m-1,n}\\ S_{m-1,n} & T_{m-1,n}\end{bmatrix}=\begin{bmatrix}Q_{m,n-1} & R_{m,n-1}\\ Q_{m,n-1}+2S_{m,n-1} & T_{m,n-1}\end{bmatrix} \end{aligned} $$ A partir de esto no es difícil obtener el resultado que necesitas.

Para una explicación conceptual, observe que $T_{m,n}=0$ para todos $m$ , $n$ . Por lo tanto, o bien todas las filas utilizan sólo dos colores, o bien todas las columnas utilizan sólo dos colores, o ambos. Si todas las filas utilizan sólo dos colores, entonces, como hay $4!=24$ colores para la primera casilla de la fila $1$ y como la coloración de las dos primeras filas de vértices está determinada por la elección de la coloración de este cuadrado, hay $24\cdot2^{m+1-2}=24\cdot2^{m-1}$ coloraciones de la cuadrícula en este caso. Del mismo modo, el número de coloraciones en el caso de que todas las columnas utilicen sólo dos colores es $24\cdot2^{n-1}$ . Utilizando la inclusión-exclusión, el número total de coloraciones de la red es $24\cdot\left(2^{m-1}+2^{n-1}-1\right)$ colores.

Answer 2

Pensé en esto durante un tiempo y llegué a una conclusión:

Número de formas de colorear = $4^{n-1}*4$ ¡!

En el caso de una cuadrícula nxn, se puede considerar que es un $(n-1)$ por $(n-1)$ rejilla con $2n-1$ vértices envueltos en él. A continuación, imagina que el $n-1$ La rejilla es ya coloreado. Mira esta foto:

Luego, para colorear la "capa" que la rodea, tenemos 2 formas de colorear los vértices de la caja unidad de la esquina inferior derecha. Luego, moviéndonos hacia arriba, se determinan todos los vértices hasta la esquina superior-derecha, ya que dos de los colores han sido definidos por la cuadrícula n-1 y la esquina inferior-derecha de cada caja es elegida por la de abajo (terminando en una de las 2 opciones para la inferior-derecha).

En la esquina superior derecha, nos encontramos de nuevo con 2 opciones, ya que tienes el vértice superior derecho de la $(n-1)$ cuadrícula y otro se colorea a partir de los determinados alrededor del borde, y luego se determina el resto de los colores.

Así, para una malla de tamaño n hay $4*(n-1)$ formas de colorear los vértices que satisfacen las condiciones anteriores.

Ahora, para n = 1, el número de formas de colorearlo tal que los colores sean diferentes con 4 colores es simplemente $4! = 4*3*2*1 = 24$ .

Así, derivamos que el número de formas de colorear una cuadrícula de n por n usando 4 colores tal que cada vértice del cuadrado unitario sea de un color diferente con 4 colores es $4^{n-1}*24$ .