Colorear tablero de ajedrez $\mathbb{Z}^2$

Question

Si cada cuadrado de la unidad de la plaza de celosía en el plano es de color negro o blanco según un conjunto de reglas, hay una manera de encontrar el máximo asintótico relación $r_n$ el número de cuadrados de color negro con el número total de plazas?

Si las reglas son que cada cuadrado negro puede tener en la mayoría de $n$ adyacente (side-by-side o de esquina a esquina) cuadrados de color negro, aquí están algunos de los resultados parciales para cada posible $n$: $$ r_0=\frac{1}{4},\quad r_1=\frac{1}{3},\quad r_2=\frac{1}{2},\quad r_3=\frac{1}{2},\quad r_4\geq\frac{3}{5},\quad r_5=\frac{9}{13},\quad r_6=\frac{4}{5},\quad r_7=\frac{8}{9},\quad r_8=1 $$

Answer 1

Usted puede ser capaz de obtener más de los límites (superior y/o inferior) por mirar esto como una coloración de un grafo y por el pensamiento acerca de cómo las proporciones relativas de negro-negro, negro-blanco, blanco y bordes en blanco se refieren a las proporciones de blanco y negro de los vértices. La proporción de negro vértices $p_b$ debe $p_{bb} + \frac{1}{2} p_{bw}$.

Para $r_7$ cada uno negro vértice debe ser adyacente a en la mayoría de las $7$ negro vértices, por lo que cada negro vértice debe ser adyacente a al menos un blanco de vértice, de modo que cada negro vértice debe estar asociada con, al menos, uno negro-blanco borde. Si todos los demás borde es de color negro-negro, a continuación, $\frac{7}{9}$ de los bordes son de color negro-negro y $\frac{2}{9}$ de los bordes son de color negro-negro, por lo que el límite superior en la proporción de negro vértices serían $\frac{7}{9} + \frac{1}{2} \cdot \frac{2}{9} = \frac{8}{9}.$ por lo Tanto $\frac{8}{9}$ es un superior y el límite inferior de $r_7$. Tal vez un enfoque similar podría darle superior de $r_k$ límites para obtener más interesante $k$.

Edit: esta respuesta no es tan útil ahora que hemos encontrado un documento que da valores exactos para todos los $k$ con la excepción de $k=4$.

Answer 2

Usted puede hacer $r_4$ $\frac{3}{5}$ relación

. . X X X. . X X X
X X... X X X. . X
. X X X... X X X.
X. . X X X. . X X
X X X... X X X. .
. . X X X. . X X X
X X... X X X. . X
. X X X... X X X.
X. . X X X. . X X
X X X... X X X. .

Esta es una respuesta para que yo pueda escribir el arte ascii.