Solutions to Lights Out

 2008-07-21 21:32:40 +0000 personal mathematics

I'll briefly introduce the Lights Out puzzle: the game is played on an n-by-n grid of buttons which, when pressed, toggle between a lit and unlit state. The twist is that toggling a light also toggles the state of its neighbors (above, below, right, left—although, on the boundary, lights have fewer neighbors). All the buttons are lit when the game begins, and the goal is to turn all the lights off.

There are two key observations: