La junta de $7\times 7$ problema

Question

Una ayuda en este problema:

En una junta de $7 \times 7$ cada cuadro está pintado de rojo o azul, de modo que en cualquier plaza en la junta tiene al menos dos vecinos de casillas de color azul. determinar como pequeños cuadros de color azul que puede estar en la junta. Dos células son vecinos si tienen un lado común. Mi progreso está tratando de pintar cuadros que la mayoría tienen sólo dos vecinos de cuadros de color azul, pero mi problema es:

¿Cómo sé que tengo el mínimo?

Hay otros ajustes con menos cuadros de color azul? Gracias.

Answer 1

Tengo un poco llevar, pero el mínimo parece ser $31$ de hecho. Por desgracia, mi método no parece generalizar muy bien, pero quizás demasiado ambicioso.

---

Tenemos un total de $49$ cajas, cada una de las cuales debe tener $2$ bordes pintados de azul, que suman un total de $98$ bordes para ser pintado de azul. Como en la esquina de la caja de sólo $2$ disponible bordes de la pintura, con estos dos bordes deben ser pintadas de color azul. Este rendimientos $8$ cajas pintadas de color azul, cada una con $3$ bordes pintados bue. Esto hace un total de $24$ bordes pintados de azul, dejando $74$ bordes sin embargo, para ser pintado de azul. La imagen de la izquierda muestra estos $8$ cajas de:

$\hspace{60pt}$$\hspace{100pt}$

Tenga en cuenta que hay $24$ cajas sin embargo, para ser pintadas que han 'exceso' de los bordes, es decir, los bordes que no necesita ser pintado de azul. Se muestra en verde en la segunda imagen. Estas son las $4$ esquinas, habiendo $2$ el exceso de los bordes de cada uno, el $12$ restante lado de las cajas, habiendo $1$ exceso de orillo de cada, e $8$ casillas adyacentes a la $4$ interior de las cajas que ya han $2$ azul bordes, habiendo $1$ exceso de borde de cada uno. Esto arroja un total de $28$ el exceso de los bordes, pero nos vamos a encontrar un par de más el exceso de los bordes más tarde.

La plaza está dividida en $4$ cuadrantes de sus diagonales. Vamos a mostrar que en cada cuadrante, por lo menos $4$ el exceso de los bordes debe ser pintado de azul. Para ello vamos a pintar la parte superior del cuadrante, intentando retratar a menos de $4$ el exceso de los bordes azules. Distinguimos $5$ de los casos, la pintura hacia una contradicción.

Ambos cuadros de color azul en la parte superior del cuadrante son adyacentes a $2$ cajas con un exceso de borde, y al menos $1$ estos $2$ cajas deben ser pintadas de color azul, por lo tanto, al menos, $2$ más de las casillas en la parte superior de la fila debe ser pintado de azul. Si pintamos $4$ más de las casillas en la parte superior de la fila azul, luego pintamos $4$ el exceso de los bordes de color azul, y hemos terminado. Así que restringir a los casos en los que la pintura $2$ o $3$ más de las casillas en la parte superior de la fila azul.

Después de pintar la parte superior de la fila, cada casilla de la fila superior debe tener al menos un borde azul. La pintura sólo dos cajas en la parte superior de la fila, sólo hay una manera de hacerlo; ver la imagen de la izquierda.

$\hspace{60pt}$$\hspace{100pt}$

A continuación, en orden para nuestro recién pintado cuadros de tener $2$ azul bordes, se deben pintar las cajas inmediatamente debajo de ellos azul, ver la imagen de la derecha. A continuación, hemos pintado $4$ el exceso de los bordes de color azul, y hemos terminado.

Finalmente pintamos, precisamente, $3$ cajas en la parte superior de la fila azul. Hasta simetría, hay $4$ formas de hacerlo, teniendo en cuenta que cada caja debe tener al menos $1$ borde azul. Se muestra en la imagen de abajo.

$\hspace{25pt}$

Cada vez que un cuadro en la parte superior de la fila sólo ha $1$ borde azul, la caja directamente debajo de él, debe ser pintado de azul. Estos necesariamente cuadros de color azul se muestra en la imagen de abajo.

$\hspace{25pt}$

En la izquierda de los dos casos, podemos ver que $5$ el exceso de los bordes están pintados de azul, y hemos terminado. Queda por demostrar que en el derecho dos casos, al menos uno más el exceso de borde debe estar pintado de azul.

En el centro a la derecha caso, estamos de hecho ya se ha realizado; en la imagen de la izquierda, a continuación, el cuadro resaltado en verde ha $3$ azul bordes, por lo que ha $1$ exceso de borde pintado de azul. Con un total de $4$ el exceso de los bordes pintados de azul, este caso está cerrado.

$\hspace{60pt}$

Para el de más a la derecha y último caso, seguimos la pintura de los bordes de color azul sin pintar $3$ bordes de la misma caja azul, hacia una contradicción. En el medio de la imagen de arriba, la única manera para el cuadro destacado a ha $2$ azul bordes sin ningún otro tipo de cajas de tener $3$ azul bordes, debemos pintar el cuadro directamente debajo de azul. Para esta recién pintado cuadro de $2$ azul bordes, al menos una de las casillas a la izquierda, a la derecha o en la parte superior debe estar pintado de azul. Estos son resaltada en color naranja en la imagen de la derecha arriba. Pero en cada caso uno o ambos de los cuadros resaltados en verde se han $3$ azul bordes, por tanto, un exceso de borde pintado de azul.

Llegamos a la conclusión de que en cada uno de los cuadrantes, hay, al menos, $4$ el exceso de los bordes pintados de azul. Con $4$ cuadrantes, esto arroja un total de $16$ el exceso de los bordes para ser pintado de azul. Por lo tanto, en total se deben pintar al menos $74+16=90$ bordes de color azul, después de haber pintado la $8$ inicial a cuadros de color azul. Pero como cada casilla sólo ha $4$ bordes, esto requiere al menos $\tfrac{90}{4}>22$ más cajas para ser pintado de azul, es decir, al menos $23$ más cajas. Junto con la inicial de $8$ cajas, esto produce un mínimo de $8+23=31$ cajas para ser pintado de azul. Este es en realidad el mínimo:

$\hspace{25pt}$

Me pregunto cuántos mínima soluciones hay...