Intereting Posts

counting full bipartite matchings
Can Legendre's theorem really help solve this equation: $ax^2+by^2=cz^2$?
Relation between the tangent to a curve and the first derivative of a function
What is infinity to the power zero
What is the index of the $p$-th power of $\mathbb Q_p^\times$ in $\mathbb Q_p^\times$
Sphere packing question AGAIN.
To Find The Exponential Of a Matrix
What are higher derivatives?
Completeness of Measure spaces
Number theory problem – show $N$ is a square when…
Convergence of square of monotone sequence implies convergence of sequence.
An Infinite Double Summation $\sum_{k=1}^{\infty} \sum_{n=1}^{\infty} \frac{1}{n^2k^2(n+k)^2}$?
Checking whether a map satisfies being homomorphism
About frullani integral
Reducibility of polynomials modulo p

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:

- Multiplication partitioning into k distinct elements
- A game with two dice
- How many different subsets of a $10$-element set are there where the subsets have at most $9$ elements?
- Number of distinct numbers picked after $k$ rounds of picking numbers with repetition from $$
- Finding the smallest set on which a group acts faithfully
- Explicit bijection between ordered trees with $n+1$ vertices and binary trees with $n+1$ leaves

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?

- What is the algorithm to generate the cards in the game “Dobble” ( known as “Spot it” in the USA )?h
- Intuitively understanding $\sum_{i=1}^ni={n+1\choose2}$
- If $A$, $B$, and $C$ are sets, the only way that $A\cup C = B \cup C$ is if $A=B$
- Number of different ways of filling $N \times 4$ rectangle with Dominoes
- Count arrays with each array elements pairwise coprime
- Why do we subtract
- Can an 8×8 square be tiled with these smaller squares?
- How many bracelets can be formed?
- How many bananas can a camel deliver without eating them all?
- counting full bipartite matchings

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.

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

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.

- Proof of $\int_0^\infty \frac{x^{\alpha}dx}{1+2x\cos\beta +x^{2}}=\frac{\pi\sin (\alpha\beta)}{\sin (\alpha\pi)\sin \beta }$
- How can adding an infinite number of rationals yield an irrational number?
- Calculate the lengths of the heights descending from triangle vertices
- Use the Contraction Mapping Principle to show that $x=\frac19\sin\left(3x\right) + \sqrt{x}$ has exactly one solution $x\geqslant\frac{8}{9}$
- Is 'clamp' a formally recognized mathematical function?
- How to properly apply the Lie Series
- Proof that if $p\equiv3\,\left(\mbox{mod 4}\right)$ then $p$ can't be written as a sum of two squares
- My incorrect approach solving this limit. What am I missing?
- Is there a conjecture with maximal prime gaps
- How to find the integral $\int_{0}^{\infty}\exp(- (ax+b/x))\,dx$?
- Let $H$ be a subgroup of $G$. Let $K = \{x \in G: xax^{-1} \in H \iff a \in H\}$. Prove that $K$ is a subgroup of $G$.
- Find the limit of $(2\sin x-\sin 2x)/(x-\sin x)$ as $x\to 0$ without L'Hôpital's rule
- Is $\mathbb{Q}/\mathbb{Z}$ isomorphic to $\mathbb{Q}$?
- upper bound on rank of elliptic curve $y^{2} =x^{3} + Ax^{2} +Bx$
- Line bundle over $S^2$