# Lights out game on hexagonal grid

I greatly enjoyed the Lights Out game described here (I am sorry I had to link to an older page because some wikidiot keeps deleting most of the page).

Its mathematical analysis is here (it's just linear algebra)

Now I just discovered a hexagonal version:

Are there any mathematical results for this version of the game, before I dig in and start the analysis myself. I have the major references including

Turning Lights Out with Linear Algebra, by M. Anderson and T. Feil (1998). Math Magazine, vol. 71, no. 4, October 1998, pp. 300-303. It's here (thanks to J.M.).

Update: I've been playing with the iPhone T-Lights hexagonal versions. I can get most of them, except for the ones where the "template" is a Y shape. Any ideas?

-

Yes there are linear algebra and graph theoretic results for this game, for any arrangement of switches and starting from all off position.

Notice that you can construct a simple graph out of the arrangement of lights, by taking the lights to be vertices, and making them adjacent in the graph if they are neighbours.

Graph theoretic:

(This can found here: Problem 17 on http://books.google.com/books?id=e99fXXYx9zcC&pg=PA42)

Proposition A: Given a simple undirected graph $G(V,E)$, with vertex set $V$ and edge set $E$, we can partition $V$ into two sets $V_1$ and $V_2$ such that

$\forall y \in V_1, \ \ |\{ x: \{x,y\} \in E \wedge x \in V_1\}| = 0 \mod 2$
$\forall y \in V_2, \ \ |\{ x: \{x,y\} \in E \wedge x \in V_1\}| = 1 \mod 2$

i.e. any vertex in $V_1$ is incident to an even number of vertices in $V_1$ and any vertex not in $V_1$ (i.e. in $V_2$) is incident to an odd number of vertices in $V_1$.

$\circ$

So selecting the vertices in $V_1$ will turn on all the lights, if we start from the all off position.

Proof:

We tackle a closely related problem.

We first show that:

Proposition B: Given a simple undirected graph $G(V,E)$, there is a partition of the vertex set of $G$, $V = V_1 \cup V_2$ such that

$\forall y \in V_1, \ \ |\{ x: \{x,y\} \in E \wedge x \in V_1\}| = 0 \mod 2$
$\forall y \in V_2, \ \ |\{ x: \{x,y\} \in E \wedge x \in V_2\}| = 0 \mod 2$

i.e. Any vertex in $V_1$ is adjacent to an even number of vertices in $V_1$ and any vertex in $V_2$ is adjacent to an even number of vertices in $V_2$.

$\circ$

The proof of Proposition B is by induction on the number of vertices in $G$.

Base cases are easy.

Suppose $G$ has $n+1$ vertices. If all the vertices of $G$ have even degree, we are done, by taking $V_2 = \emptyset$.

Suppose $o$ is a vertex with odd degree and let $o_1, o_2, \cdots, o_k$ be the neighbours of $o$.

Form a graph $G'$ as follows: If $o_i$ and $o_j$ are adjacent in $G$, they are not adjacent in $G'$ and vice versa. Also delete $o$.

$G'$ is a graph with $n$ vertices.

Apply the induction hypothesis to $G'$. Say we get a partition $V' = X \cup Y$.

Now $o$ must be incident to an even number of vertices in one of $X$ or $Y$. Say $X$. Add $o$ to $X$ to get a partition for $G$. We can easily show that this partition of $G$ is what we need.

$\square$

Now to apply this to our problem (Proposition A):

Add a new vertex $N$ to G and make it adjacent to every vertex of even degree in $G$ to get a new graph $G'$.

Apply Proposition B to $G'$. Suppose the partition satisfying proposition B is $V = X \cup Y$. We can easily show that this is also the partition in $G$ (ignoring $N$) for proposition A.

Note: This not only proves the existence of a solution, but the induction proof actually gives you an O(n^3) time algorithm to find the solution.

Linear Algebra Proof due to Noga Alon:

Over $\mathbb{F}_2$, let $A$ by any $n\times n$ symmetric matrix. We can show that if $d$ is the diagonal vector of $A$, then $d$ is in the space spanned by the rows of $A$.

This follows from the identity (valid over $\mathbb{F}_2$) that

$v^{T}Av = d^{T}v$, where $u^{T}$ is the transpose of $u$.

Thus if $v$ is in the null space of $A$, then $d$ is orthogonal to $v$ and as a consequence, $d$ is in the row space of $A$.

We consider the matrix A to be $B+I$ where $B$ is the adjacency matrix of the corresponding graph we get, from the arrangement of the lights.

-
I've tried apply this theorem on the standard lights out and failed. Pressing all buttons in V1 failed to solve. Is there something missing? –  John Smith Nov 21 '10 at 17:01
@John: What was the V1 you found? –  Aryabhata Nov 21 '10 at 17:03
It was all the buttons except the edge buttons not in the corners. The reason I think there is something missing (or the theorem is for something else) is because the solution to the standard 5x5 case is very nonsymmetric. Look at it here: orion.math.iastate.edu:80/burkardt/puzzles/… –  John Smith Nov 21 '10 at 17:49
That can't be the V1 in Proposition A. The corner buttons are adjacent to and even number of buttons in V1. –  Aryabhata Nov 21 '10 at 17:56
I think you misunderstood. I did include the corner buttons. Let me try to draw V1: I go row by row. The X is the button I press, the - is the button I don't press x---x, -xxx- , -xxx- , -xxx- , x---x –  John Smith Nov 21 '10 at 17:58

Here is another version of this game. You have a symmetric matrix $A$ over $GF(2)$ (i.e. $0,1$ with all computations done modulo $2$). Then you can show that the diagonal of $A$ is always in the range of $A$, and this is best possible in the sense that the range of $A$ could consist of only the zero vector and the diagonal of $A$.

I was actually given this "game" as a riddle, so I wouldn't ruin it for you with an answer.

EDIT: Here's my answer, which is probably very similar to Moron's proof. Of course Noga's proof is much neater, but it's not algorithmic (in any other respect it's much better).

-