Maximizing Edges in the Lights Out Game*

Abstract: Lights Out was a game by Tiger Electronics released in 1995. The game consisted of a 5x5 grid of buttons that could be on or off. Some of the buttons start as on, and the goal is to turn all the lights off by pushing buttons. When a button is pushed, that light and its 4 neighbors on the grid are "toggled" meaning, on switches to off and off switches to on. This game can be generalized to being played on a graph with labels from $\mathbb{Z}_\ell$, where "toggling" now means increasing the label of the vertex by 1 (modulo $\ell$). The game is won when all the labels reach $0$. This game is not winnable for every graph with every initial set of labels. We ask, for an $n$ vertex graph, what is the maximum number of edges in a graph that is winnable for every set of initial labels from $\mathbb{Z}_\ell$? We find the answer when at least one of $n$ or $\ell$ is odd, and in several additional cases.

Back to Search Research Symposium Abstracts