Número esperado del mismo color regiones en un suelo de baldosas

Question

Supongamos que tenemos una planta rectangular, $a$ unidades de largo por $b$ unidades de ancho, que necesitamos de baldosas negras y blancas de la unidad de baldosas cuadradas. Lanzamos una moneda para decidir si la primera baldosa será de color negro o blanco, y la pongo en la esquina superior izquierda. La segunda y todas las baldosas también tendrá una 50-50 posibilidad de ser en blanco y negro.

Una 'región' se define como un área contigua del mismo color de las baldosas, tocarse el uno al otro por sus lados (sólo una esquina no es suficiente). Por lo tanto, el número máximo de regiones es posible es $ab$ (de tablero de ajedrez de mosaico), mientras que el número mínimo es de 1 (todo el piso es negro o blanco).

¿Cuál es el número esperado de las regiones en el consejo, como una función de $a$$b$?

Answer 1

Al principio no lo voy a tomar los bordes en cuenta. Supongamos que la junta se envuelve alrededor, en forma de un toro.

El número esperado de 1-plaza de las regiones es $ab/2^4$ porque todos los cuatro bordes debe ser el color opuesto.

El número esperado de la vertical dominó es $ab/2^7$, como a los seis bordes y el interior de un partido debe ser correcta. Lo que es el número de la horizontalidad de las fichas de dominó, así que le da $2ab/2^7$ 2-plaza de las regiones.

Para triominoes, hay ocho bordes y dos líneas internas. La L triomino tiene cuatro orientaciones, y el me triomino tiene dos, así que usted consigue $6ab/2^{10}$ tres-plaza de las regiones.

Para tetrominoes por, I se $18ab/2^{13}$. La plaza contribuye $ab/2^{12}$, y los otros varios múltiplos de la $ab/2^{13}$.

El total se parece a $$ab\left[\frac1{16}+\frac2{128}+\frac6{1024}+\frac{18}{8192}+\cdots\right]$$

Así que parece que sólo una pequeña parte de la zona - es decir, una cuarta parte está cubierto de pequeñas regiones.

Usted obtener un rectángulo de un toro por corte a lo largo de una línea horizontal y una línea vertical para hacer los bordes. Algunos de estos polinomios se corta en dos pedazos. Que le da un extra de $$(a+b)\left[\frac0{16}+\frac1{128}+\frac6{1024}+\frac{23}{8192}+\cdots\right]$$ Algunos polyominos, incluyendo el U-pentomino, se cortan en tres o más piezas. Asimismo, la plaza tetromino y P-pentomino se puede cortar en cuatro trozos si ellos terminan en las cuatro esquinas del rectángulo.

Answer 2

En el caso de un tablero de ajedrez, el número de regiones es, simplemente,$ab$.

Cuando dos adyacentes cuadrados son del mismo color, esto reduce el número de regiones por 1. Hay $a$($b$-1) + $b$($a$-1) total de conexiones posibles entre dos adyacentes plazas. Para cualquier par de fichas adyacentes, hay un 50% de probabilidades de que son del mismo color. En consecuencia, se espera que el número de conexiones es simplemente $ab$ - ($a$+$b$)/2. Ahora nos resta este de el número total de baldosas. Por lo tanto, se espera que el número de regiones es ($a$+$b$)/2 .

Sin embargo, considere el caso de un 2*2 cuadrado de 4 azulejos son todos del mismo color. Aquí, hay 4 fichas y 4 del mismo color de las conexiones entre los azulejos. Sin embargo, el número de regiones que no es 4-4=0, sino más bien, es 1. En consecuencia, para todos los del mismo color cuadrado que aparece, tenemos que añadir un 1 al conde de las regiones. Para cualquier 2*2 metros, hay un 1/8 posibilidad de que todas las piezas sean del mismo color. Hay ($a$-1)($b$-1) total de plazas, por lo que un valor esperado de ($a$-1)($b$-1)/8 del mismo color de los cuadros.

Juntando las piezas, se espera que el número de regiones que se simplifica a: (($a$+3)($b$+3)/8) - 1.