Note on the lamp lighting problem

2004/11/09 by Henrik Eriksson, Kimmo Eriksson, Jonas Sjostrand · 2 citations
Mathematics · #math.CO #msc:05C50 #msc:05B45 #msc:52C20 #msc:11C20 #msc:15A36 #msc:68Q80

paper · pdf

published as Advances of Applied Mathematics 27, 2001, pages 357-366 · 10 pages

arxiv created 2004/11/09 · arxiv updated 2009/12/01

Abstract

We answer some questions concerning the so called sigma-game of Sutner. It is played on a graph where each vertex has a lamp, the light of which is toggled by pressing any vertex with an edge directed to the lamp. For example, we show that every configuration of lamps can be lit if and only if the number of complete matchings in the graph is odd. In the special case of an orthogonal grid one gets a criterion for whether the number of monomer-dimer tilings of an m times n grid is odd or even.

Cited by

• Lights Out Puzzle in p Colors: Evolution of Quiet Patterns
• Lights Out On Nearly Complete Graphs

Related

• Completely symmetric configurations for sigma-games on grid graphs
• Difference between minimum light numbers of sigma-game and lit-only sigma-game
• Resolution of Conjectures Related to Lights Out! and Cartesian Products
• An Inductive Proof that Lights Out Configurations are Invertible, and a Parity-Invariance Result
• Resolution to Sutner's Conjecture