Demostrar que todas las bombillas de luz no se puede apagar la luz

Question

Se nos da una tabla de dimensiones $2010\times2012$ donde cada celda tiene una bombilla de luz. Al principio, el número de "en" bombillas de luz es mayor que $2009\times2011$. Si en cualquier parte de la tabla de dimensiones de $2\times2$ hay tres "off" bombillas de luz, luego el cuarto de la bombilla es también apagado. De lo contrario, no pasa nada. Demostrar que al menos una bombilla se enciende en la final.

Pensé por primera vez en dividir la tabla en $2\times2$ partes, pero no estoy seguro de cómo hacerlo. Después de que me encontré con que $2010\times2012-(2009\times2011+1)=2011^2-1-2010^2=4020$ que es el máximo de las bombillas de luz apagado. No tengo idea de a dónde ir a partir de este. Cualquier ayuda/sugerencias se agradece.

Answer 1

Como se indica en la pregunta, el número máximo de bombillas al principio es dos veces el número de filas, y dos menos que el número de columnas.

Nuestro peor de los casos aquí se ve como este, donde la $0$ es una bombilla que se apaga y $1$ es en:

\begin{bmatrix} 0 & 0 & 1 & 1 & 1 & \ldots & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & \ddots & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & \ddots & \ddots & 1 \\ \vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 1 & 1 & \ddots & \ddots & \ddots & \ddots & \ddots & 1 \\ 1 & 1 & \ldots & \ldots & 1 & 0 & 0 & 1 \end{bmatrix}

En esta configuración, tenemos dos diagonales de bombillas de lado a lado. Cada $1$ tocando a la diagonal (a excepción de la $1$s en la última columna, la mente!) puede ser "atacado" por los tres $0$s que comparten una $2 \times 2$ plaza con ella, y entonces sus vecinos puede ser atacado, y así sucesivamente. Esto todavía deja la última columna completamente porque no hay manera de atacarlo.

Tenga en cuenta que si hay una ruptura en las diagonales de $0$s en el escenario del "peor caso" de arriba, a continuación, todas las bombillas no se apaga, porque vamos a tener una configuración como esta dentro de nuestra $2010 \times 2012$ matriz:

\begin{bmatrix} 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ \end{bmatrix}

Observamos aquí que no hay manera de atacar el $1$s en $2 \times 2$ cuadrado en el centro, ni el $1$s de mar en las plazas que se extiende desde el centro.