Intereting Posts

Constructing a choice function in a complete & separable metric space
Information on “stronger form” of Dirichlet's Theorem on Arithmetic Progressions
Subgroups of $D_4$
Euler's Totient function $\forall n\ge3$, if $(\frac{\varphi(n)}{2}+1)\ \mid\ n\ $ then $\frac{\varphi(n)}{2}+1$ is prime
Does the series $\sum n!/n^n$ converge or diverge?
How to prove a topologic space $X$ induced by a metric is compact if and only if it's sequentially compact?
Show $f^*dx_i = \sum_{j=1}^l \frac{\partial f_i}{\partial y_j} dy_j = df_i$
Square root of a Mersenne number is irrational
Prove that $0 \leq ab + ac + bc – abc \leq 2.$
Showing that a function is of class $C^{\infty}$
Are there any objects which aren't sets?
Proving $ 1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$ for all $n\geq 2$ by induction
Proving $a^ab^b + a^bb^a \le 1$, given $a + b = 1$
Frog Jump Problem
Proof of $(a+b)^{n+1}$

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:

- Xmas Combinatorics 2014
- Determining the position of a binary value with $k$ one bits and $n-k$ zeros in an enumeration of $C_k^n$ bit strings
- Probability of combinatorics
- Proving formula for sum of squares with binomial coefficient
- How to find unique multisets of n naturals of a given domain and their numbers?
- Proving that $\sum\limits_{k=0}^{n} {{m+k} \choose{m}} = { m+n+1 \choose m+1 }$

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?

- “Binomiable” numbers
- Stirling Numbers of the First Kind - a direct derivation
- Combinatorics Distribution - Number of integer solutions Concept Explanation
- Probability problem
- Combinatorial proof of the identity ${n+1\choose k+1}={k\choose k}+{k+1\choose k}+…+{n-1\choose k}+{n\choose k}$
- Big-O Notation - Prove that $n^2 + 2n + 3$ is $\mathcal O(n^2)$
- Verifying Touchard's Identity
- Mathematical Induction for Recurrence Relation
- Partitioning $\{1,\cdots,k\}$ into $p$ subsets with equal sums
- Tiling a $3 \times 2n$ rectangle with dominoes

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.

- Prove that $\frac{x^x}{x+y}+\frac{y^y}{y+z}+\frac{z^z}{z+x} \geqslant \frac32$
- Proving a sequence is Cauchy given some qualities about the sequence
- Ideal and minimal polynomial
- If $S$ is a finitely generated graded algebra over $S_0$, $S_{(f)}$ is finitely generated algebra over $S_0$?
- Extension of bounded convex function to boundary
- Number of transitive acting groups on four letters?
- Complex polynomial and the unit circle
- A separable locally compact metric space is compact iff all of its homeomorphic metric spaces are bounded
- The space obtained by identifying the antipodal points of a circle
- Showing $\sup \{ \sin n \mid n\in \mathbb N \} =1$
- Show that a locally compact Hausdorff space is regular.
- Find: $ \int^1_0 \frac{\ln(1+x)}{x}dx$
- Is any closed ball non-compact in an infinite dimensional space?
- Dirichlet L-series and Gamma function question
- Prime divisors of the conductor of an order of an algebraic number field