Prove that all light bulbs can't light off
We are given a table of dimensions $2010\times2012$ where every cell has one light bulb. At the beginning, the number of "on" light bulbs is greater than $2009\times2011$. If in any part of table dimensions $2\times2$ there are three "off" light bulbs, then the fourth light bulb is also turned off. Otherwise nothing happens. Prove that at least one light bulb is turned on at the end.
I first thought splitting the table into $2\times2$ parts but I'm not sure how to do so. After that I found that $2010\times2012-(2009\times2011+1)=2011^2-1-2010^2=4020$ which is the maximum of light bulbs turned off. I have no idea where to go from this. Any help/hints are appreciated.
Solution 1:
As stated in the question, the maximum number of bulbs off at first is twice the number of rows, and two less the number of columns.
Our worst case scenario here looks like this, where $0$ is a bulb that's off and $1$ is on:
\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}
In this configuration, we have two diagonals of off bulbs side by side. Every $1$ touching the diagonal (except for the $1$s in the last column, mind you!) can be "attacked" by the three $0$s that share a $2 \times 2$ square with it, and then its neighbors can be attacked, and so on. This still leaves the last column completely on because there's no way to attack it.
Note that if there is a break in the diagonals of $0$s in the "worst case scenario" above, then all the bulbs won't turn off, because we will have a configuration like this within our $2010 \times 2012$ matrix:
\begin{bmatrix} 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ \end{bmatrix}
Observe here that no way to attack the $1$s in the $2 \times 2$ square in the middle, nor the $1$s behind them in squares extending away from the center.