13
$\begingroup$

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:

http://cwynn.com/games/lightsoutmobile.htm
(and hopefully soon) https://sites.google.com/site/beyondlightsout/

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?

  • 0
    I tried to comment on the original question, but I don't have enough rep. I made mobile versions of this game, Hexagonal Lights Out: - Android: https://play.google.com/store/apps/details?id=com.lgs.hlo&hl=en - iOS: https://itunes.apple.com/pt/app/hexagonal-lights-out/id831852843?mt=8 Let me know if you'd appreciate a web version.2017-11-25

3 Answers 3

9

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.

  • 0
    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?2010-11-21
  • 0
    @John: What was the V1 you found?2010-11-21
  • 0
    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: http://orion.math.iastate.edu:80/burkardt/puzzles/lights_out_solution.html2010-11-21
  • 0
    That can't be the V1 in Proposition A. The corner buttons are adjacent to and even number of buttons in V1.2010-11-21
  • 0
    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---x2010-11-21
  • 0
    @John: The button next to the corner has even number of neighbours in V1.2010-11-21
  • 0
    What's the reference for the theorem. The certainly is a lot more in the hypothesis. How is the switch flipping action taken into account.2010-11-21
  • 0
    @John: I have edited the answer with a reference.2010-11-21
  • 0
    @Moron . I read the result. It doesn't say anything about that the vertices in V1 will switch all the lights, just that switching some of the buttons.2010-11-21
  • 0
    @John: Did you read my previous comment? The V1 you have seems incorrect: "The button next to the corner has even number of neighbours in V1". Also, if you look at proposition A, it should be _very easy to see_ that clicking on the V1 lights will turn all of them on.2010-11-21
  • 0
    @Moron Look at the correct solution for the lights out I pointed. I have worked hard on getting all the solutions. That solutions have very little to do with V1. It is **not** easy to see the solution. Try it yourself.2010-11-21
  • 0
    @John: The V1 you have is incorrect. Please don't draw incorrect conclusions based on the V1 you have. 17c in the problem I linked is exactly the same problem, starting from all off state.2010-11-21
  • 0
    @Moron I am sorry I misunderstood V1. The whole point of Lights Out is **finding** V1, and unfortunately that theorem does not help.2010-11-28
  • 0
    @John: It helps, the inductive proof gives actually gives you an algorithm. In any case, you had asked for mathematical results in your question. I don't see any indication in the question that you were looking for an algorithm. If you wanted an algorithm (which you got btw) you should have mentioned it!2010-11-28
  • 0
    Hi @Aryabhata, how do you perform the time analysis to get $O(n^2)$? My naive approach only gives me $O(n^3)$ because constructing $G'$ from $G$ may take time $O(n^2)$ if the degree of the node is $\Theta(n)$.2013-04-23
  • 0
    @Hsien-ChihChang張顯之: You are right. My "naive" approach gave me $O(n^2)$ :-) I will correct it. Thanks for pointing that out.2013-04-23
3

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).

3

I tried (and tried again) to improve the Wikipedia article but the edits were promptly reverted as if well-known solutions of Lights Out are "original research", despite providing several citations.

If any Stack Exchange members are Wikipedians who can assist in restoring the article, it would be greatly appreciated. Also, I would direct this request more appropriately if I could, but don't see a way to contact John Smith directly. Feel free to delete it.

  • 2
    I feel your pain. Someone on wikipedia is on a power trip.2010-11-28
  • 0
    I sympathize greatly; I stopped trying to improve Wikipedia after a bunch of jerks undid all my edits.2010-11-29