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 |