The puzzle description is: here.
In brief: An $N\times N$ grid of lights, touching a light toggles all lights in the same row and column as that light. Give a formula for number of initial states of lights which can be all turned off.
Solution
There are two cases, when $N$ is even and $N$ is odd.
When $N$ is even, you can toggle a single light by touching all the lights in the same row and same column as that light.
Thus, any initial grid can be turned all off by targeting only the lights that are on.
So for even $N$ the formula is $2^{N^2}$ (any grid, basically).
The harder case is when $N$ is odd. There are in fact initial combinations which cannot be turned off (for e.g, the example posted in the problem blog post).
There is a nice invariant of the operation which we can use.
Suppose you treat an on light as $1$ and off as $0$.
Consider the sum over $\mathbb{F}_2$ (i.e. modulo $2$) of the numbers for each row (say $R_i$ for row $i$) and each column (say $C_j$ for column $j$). The possible values of $R_i$ and $C_j$ are $1$ and $0$ (remember: modulo $2$ or $\mathbb{F}_2$).
Then, the touching a light operation, toggles all the $R_i$ and $C_j$ at once: i.e. if $R_i$ was $1$ it becomes $0$ and vice-versa, try it out.
Thus for an initial grid to be able to be turned off, we need $R_i = C_j$ for all $i, j$, as the final grid has $R_i = C_j = 0$.
This is also a sufficient condition, and we can prove it as follows:
Proof:
Assume the grid has $R_i = C_j$ initially.
Suppose $N = 2k+1$. Then consider the $2k \times 2k$ grid formed by the topmost $2k$ rows and the leftmost $2k$ columns.
By our observation about even $N$, we can turn that grid off completely just by touching lights within that grid.
This will result in the last row and last column to have some lights on/off depending on the lights that were touched in the $2k\times 2k$ portion.
But since we started out with $R_i = C_j$ and the light touching operation does not change that, the last row and last column must all be ones, or all be zeroes. In which case the whole $(2k+1)\times (2k+1)$ grid can be turned off: if the last row and column are all ones, we just touch the bottom right light.
$\blacksquare$.
This also allows us to count: Fill in the $2k \times 2k$ grid arbitrarily. The rest of the number are forced.
Thus for odd $N = 2k+1$, the formula we are looking for is $2^{4k^2} = 2^{(N-1)^2}$.
In brief: An $N\times N$ grid of lights, touching a light toggles all lights in the same row and column as that light. Give a formula for number of initial states of lights which can be all turned off.
Solution
There are two cases, when $N$ is even and $N$ is odd.
When $N$ is even, you can toggle a single light by touching all the lights in the same row and same column as that light.
Thus, any initial grid can be turned all off by targeting only the lights that are on.
So for even $N$ the formula is $2^{N^2}$ (any grid, basically).
The harder case is when $N$ is odd. There are in fact initial combinations which cannot be turned off (for e.g, the example posted in the problem blog post).
There is a nice invariant of the operation which we can use.
Suppose you treat an on light as $1$ and off as $0$.
Consider the sum over $\mathbb{F}_2$ (i.e. modulo $2$) of the numbers for each row (say $R_i$ for row $i$) and each column (say $C_j$ for column $j$). The possible values of $R_i$ and $C_j$ are $1$ and $0$ (remember: modulo $2$ or $\mathbb{F}_2$).
Then, the touching a light operation, toggles all the $R_i$ and $C_j$ at once: i.e. if $R_i$ was $1$ it becomes $0$ and vice-versa, try it out.
Thus for an initial grid to be able to be turned off, we need $R_i = C_j$ for all $i, j$, as the final grid has $R_i = C_j = 0$.
This is also a sufficient condition, and we can prove it as follows:
Proof:
Assume the grid has $R_i = C_j$ initially.
Suppose $N = 2k+1$. Then consider the $2k \times 2k$ grid formed by the topmost $2k$ rows and the leftmost $2k$ columns.
By our observation about even $N$, we can turn that grid off completely just by touching lights within that grid.
This will result in the last row and last column to have some lights on/off depending on the lights that were touched in the $2k\times 2k$ portion.
But since we started out with $R_i = C_j$ and the light touching operation does not change that, the last row and last column must all be ones, or all be zeroes. In which case the whole $(2k+1)\times (2k+1)$ grid can be turned off: if the last row and column are all ones, we just touch the bottom right light.
$\blacksquare$.
This also allows us to count: Fill in the $2k \times 2k$ grid arbitrarily. The rest of the number are forced.
Thus for odd $N = 2k+1$, the formula we are looking for is $2^{4k^2} = 2^{(N-1)^2}$.
No comments:
Post a Comment