That would at least tell you which grid sizes have a guaranteed solution. I would try to investigate the determinant of these matrices in the abstract case and see if you come up with anything. Given initial the grid with random states, the objective is to set all cells to off state. You can swap the state of any cell, but when you do so, the adjacent cells (horizontally or vertically) are swapped as well. So the answer is that all $2\times2$ grids are solvable, and there's the solution (concurring with Aryabhata's proposition).Īs the number of equations is equal to the number of cells on the grid, this method quickly becomes too tedious and complicated to perform by hand. Lights Out is a grid-based puzzle where each cell has two states: on/off. Gaussian Elimination works easily on this matrix (tip: remember that mod $2$, $a a = 0$ for any $a$) and we obtain an explicit solution for the general $2\times2$ grid: The matrix for this system looks like this (omitting zeros for readability): To the switch at position $i, j$ make correspond a variable $s_$, we therefore need to solve: Flipping a switch has the effect of adding $1$ to each corresponding light, modulo $2$. Think of each light as a variable taking values in $0, 1$. If $m$ and $n$ have different parities, there is more work to be done. Now, the above can be generalized to the $m \times n$ case, when $m$ and $n$ have the same parity. Now we toggle the bottom right corner, if needed. Since the row and column parities all flip together and were initially all the same, we must have that the remaining lights, in the bottom row and right column, are all the same (including the bottom right corner). Use the above even $n$ case algorithm to switch off all the lights in that $2k\times 2k$ grid. To prove sufficiency, consider an arrangement of $(2k 1)\times(2k 1)$ which has all row and column parities the same.Ĭonsider the $2k\times 2k$ subgrid which does not include the bottom row and the right column. This shows the necessity of the parities being the same. Thus if they are not all the same, we can never achieve all lights off. Notice that if $n$ is odd, on any single operation, all the row and column parities change simultaneously. You can toggle just a particular light by toggling all The sum of each individual row, and sum of each individual column must if the lights were $1$ for on and $0$ for off, then modulo $2$, If $n$ is odd, there is a solution iff the 'on' lights parities for If $n$ is even, there is always a solution given any starting
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |