Lights Out: a puzzle you can prove impossible
Tonight's idea
A Lights Out board is a grid of lights. Pressing a cell toggles it and its up, down, left and right neighbours, with no wrapping at the edges. The goal is every light off.
Pressing a cell twice undoes it, so each cell is pressed once or never. A light only cares how many times it was toggled, so order does not matter. A plan is a set of cells: a vector \(x\) of 0s and 1s.
Write 1 for on, 0 for off, and add the odd way: \(1 + 1 = 0\), since two toggles cancel. That is arithmetic mod 2, the parity rule. Each press is a column recording which lights it toggles. The columns form a matrix \(A\), and clearing a board \(b\) means solving
\(A x = b \pmod 2\): the matrix equations you have met, but over bits.
Pressing the four corners and the centre clears the all-on \(3 \times 3\) board. A corner is toggled once, an edge cell three times (two corners and the centre), the centre once. All odd, so every light goes off.
Watch one: a \(2 \times 2\) board, top-left on
Call the presses \(p_1, p_2, p_3, p_4\) (top-left, top-right, bottom-left, bottom-right). Each light lists the presses that reach it, and the right-hand side is the starting board:
\[p_1 + p_2 + p_3 = 1, \qquad p_1 + p_2 + p_4 = 0, \qquad p_1 + p_3 + p_4 = 0, \qquad p_2 + p_3 + p_4 = 0.\]
Eliminate with row XOR, no minus signs needed since \(-1 = 1\). Add row 1 into rows 2 and 3: \(p_3 + p_4 = 1\) and \(p_2 + p_4 = 1\). Add that new row 3 into row 4: \(p_3 = 1\). Back-substitute: \(p_4 = 0\), \(p_2 = 1\), \(p_1 = 1\). Press top-left, top-right and bottom-left. Check: the top-left light is toggled three times and goes off; every other light is toggled twice and stays off.
Play it, get a hint, or see the solver's plan: mathdetours.com/demos/lightsout.html.
Your turn
- On a \(3 \times 3\) board only the centre light is on. Find a set of presses that clears it, and check every light.
- How many press plans are there on a \(3 \times 3\) board? No non-empty plan leaves the board unchanged, so different plans give different boards. Use the pigeonhole principle to deduce that every \(3 \times 3\) board can be cleared, in exactly one way.
- On the \(4 \times 4\) mask, press row 3, column 2 and list the marked cells that toggle. Repeat for the top-left and bottom-right presses. Then check all sixteen presses: each toggles an even number of marked cells.
- The number of lit marked cells is odd or even. Explain why no press can change that parity, and deduce that the \(4 \times 4\) board with only the top-left light on can never be cleared. Which other single-light boards does the mask rule out?
Stretch: all the masks
A mask \(z\) works when \(z^{\mathsf T} A = 0 \pmod 2\). Show that the mirror image of the given mask also works, and that if two masks work then their XOR works too. The \(4 \times 4\) masks form a group under XOR. How many are there, if \(A\) has rank 12 out of 16?
Answers
- Press the centre and the four edge-middle cells, a plus sign. The centre is toggled 5 times and goes off. Each edge cell is toggled twice (itself and the centre), each corner twice (its two edge neighbours), so they stay off.
- Each of 9 cells is pressed or not: \(2^9 = 512\) plans. They produce 512 different boards, and there are only \(2^9 = 512\) boards in all, so every board is produced by exactly one plan. In matrix language, \(A\) has rank 9: it is invertible mod 2.
- Pressing row 3, column 2 toggles (3,1), (3,2), (3,3), (2,2) and (4,2); the marked ones are (3,1), (3,2), (3,3), (4,2): four. Top-left toggles (1,1), (1,2), (2,1); marked: (1,1), (1,2), two. Bottom-right toggles (4,4), (3,4), (4,3): none marked, zero. All sixteen presses toggle 2 marked cells, except row 3, column 2 (4) and bottom-right (0).
- A press toggles an even number of marked cells, so the count of lit marked cells changes by an even amount and its parity is fixed. The top-left light sits on a marked cell: one lit marked cell, odd. The cleared board has zero, even. No sequence of presses connects them. The mask rules out every single-light board whose light is on a marked cell: 8 of the 16. (The other 8 are impossible too, but need another mask.)
Stretch. The mirror mask (rows 1011, 1000, 0111, 0010) also toggles evenly under every press. If \(z^{\mathsf T} A = 0\) and \(w^{\mathsf T} A = 0\) then \((z + w)^{\mathsf T} A = 0\) mod 2, so masks are closed under XOR; the empty mask is the identity and each mask is its own inverse. Rank 12 leaves \(16 - 12 = 4\) independent masks, hence \(2^4 = 16\) masks in all, including the empty one. The same count says only \(2^{12} = 4096\) of the 65 536 boards can be cleared: one in sixteen.