This is similar to the Lights Out game, and is actually based on a problem from an old Bay Area Maths Olympiad I had seen.
You have an $N \times N$ grid of lights, each light is either on or off (different lights could be in different states).
When you touch a light, all the lights in the same row and same column as that light toggle, i.e. if they were on, they turn off and vice-versa.
For example, say the grid was
$$\begin{bmatrix} \blacksquare & \blacksquare & \Box\\\Box & \Box & \Box\\ \Box & \blacksquare & \Box \end{bmatrix}$$
Now if you touch the light in the top left corner, it becomes
$$\begin{bmatrix} \Box & \Box & \blacksquare \\ \blacksquare & \Box & \Box \\ \blacksquare & \blacksquare & \Box \end{bmatrix}$$
The goal of the lights out puzzle is usually to turn all the lights off by some sequence of touches, given a starting grid.
This problem is slightly different.
Given an $N$, you need to give a formula for exactly how many grids can be converted to all off by some sequence of touches. The already all off grid should also be counted.
[Note: Rotations of the same grid etc are considered to be different, so there are a total of $2^{N^2}$ grids.]
[Solution]
You have an $N \times N$ grid of lights, each light is either on or off (different lights could be in different states).
When you touch a light, all the lights in the same row and same column as that light toggle, i.e. if they were on, they turn off and vice-versa.
For example, say the grid was
$$\begin{bmatrix} \blacksquare & \blacksquare & \Box\\\Box & \Box & \Box\\ \Box & \blacksquare & \Box \end{bmatrix}$$
Now if you touch the light in the top left corner, it becomes
$$\begin{bmatrix} \Box & \Box & \blacksquare \\ \blacksquare & \Box & \Box \\ \blacksquare & \blacksquare & \Box \end{bmatrix}$$
The goal of the lights out puzzle is usually to turn all the lights off by some sequence of touches, given a starting grid.
This problem is slightly different.
Given an $N$, you need to give a formula for exactly how many grids can be converted to all off by some sequence of touches. The already all off grid should also be counted.
[Note: Rotations of the same grid etc are considered to be different, so there are a total of $2^{N^2}$ grids.]
[Solution]
No comments:
Post a Comment