Universal configurations in light-flipping games (Q2768402)

The paper considers a generalization of two closely related mathematical problems, spawned by electronic games, called the light flipping games. It establishes a characterization of a class of solutions to the games, which subsumes known results for the specialized versions.NEWLINENEWLINENEWLINELet \(G\) denote an undirected \(n\)-vertex graph, each of whose nodes has an indicator light which can be switched to an ON or OFF position with a button which are of two types: exclusive (pressing it with switch the state of all the neighbouring nodes but not that of the node itself) or inclusive (pressing it will switch the state of all the neighbouring nodes and that of the node itself). Let \(b\) denote the vector of button pattern, i.e., \(b_v= 0\) if the button at node \(v\) is exclusive and \(b_v= 1\) if it is inclusive. By a configuration (of lights) is meant a vector \(c\) with \(c_v= 1\) or \(0\) depending on whether the node \(v\) is in the ON or OFF position. A configuration \(c\) is called universal for a button pattern \(b\) if \(c\) can be truned off, i. e., by pressing a finite sequence of button all of them can be brought to the OFF position. The main theorem shows that, aside from the (trivial) all OFF configuration, the only universal configuration is the one where the inclusive buttons, and only those, are in the ON position. It may be stated as follows:NEWLINENEWLINENEWLINETheorem: The only universal configurations \(c\) for a given button pattern \(b\) are \(c= 0\) and \(c= b\).NEWLINENEWLINENEWLINEThe proof involves looking at the problem as one of existence of solutions to a class of systems of linear equations.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].