Lightbulb puzzle related to proofs by induction.

Question

The puzzle question was as follows: There is a circle of $n > 2$ lights with a switch next to each of them. Each switch can be flipped between two positions, thereby triggering the on/off states of three lights: it's own and the two lights adjacent to it. Initially all the lights are off, how can one turn all the lights on by flipping the minimum amount of switches.

Now I figured out that for all $n > 2$, one can simple start on any one of the switches, and move clockwise say, pressing each switch as you go, after pressing the last switch, i.e the one before the switch you pressed first, all the switches will be on. This wouldn't be the solution with the minimum amount of switch flipping though.

Here's my sketch of a proof by induction that this works for all $n>2$:

An $n$-chain, is is chain of switches linked to each other as follows: switch - switch - switch - ... - switch. Pressing any switch toggles the switch's own state, and the state of any neighbors in the chain.

Lemma: For any $n$-chain, where $n>2$, pressing the switch for light 1, then light 2, etc. upto the last light results in the following pattern: off - on - on - ... - on - off.

We proceed by induction on $n$:

(Base Case) For $n = 3$, the switches are as follows after each move:

off - off - off (Initial state)
on  - on  - off (After pressing first switch)
off - off - on  (After pressing second switch)
off - on - off (After pressing last swich)

(Inductive Case) Suppose that the theorem works for $n$-chains, we need to show that it works for $(n + 1)$ chains. Consider what happens when we press the n-th switch of an $n+1$ chain, after pressing switches $1...(n - 1)$, since switches $1 ..n$ form an $n$-chain, pressing the n-th switch will result in switch 1 being off, switches $2..(n-1)$ being on and switch $n$ being off, by the inductive hypothesis. Furthermore, since switch $n$ is connected to switch $n + 1$, switch $n+1$ will be switched on, resulting in a pattern that looks like this: off - on - on - on ... - off - on After pressing switch $n+1$, switch $n$ toggles from off to on, and switch $n+1$ toggles from on to off resulting in a pattern that looks like this: off - on - on - ... - on - off.

Since the theorem is true for $n = 3$ and it's truth for any $n$ implies it's truth for $n+1$, the theorem is true for any $n > 2$ by mathematical induction on $n$. QED

Now any circle of switches can be decomposed into an $n$-chain and a switch connected to it's end points as follows:

------switch ------
|                 |
switch-switch-switch

Call the leftmost bulb of the $n$-chain, switch one, the next one in the $n$-chain, switch two and so on, all the way to the non-$n$-chain switch, which will be labelled switch $n$ of course. By the above lemma, pressing switches $1$ to $n-1$, will result in the following pattern:

----------off -------
|                  |
off-on-on-......-off

Pressing switch n, will therefore turn it on, and the two endpoints of the $n$-chain, on, turning on the whole circle of chains. QED.

I have five questions,

1. Is the above informal proof, easy to follow, if it isn't how can I make it more readable.
2. Since I am sympathetic to formalism in mathematics, how can I formalize this proof, pretty much the only part that doesn't feel hand wavy is the base case of the lemma.
3. I know that in an circle of $n$ switches, where $n$ is a multiple of three, one can just divide the switches into groups of three, and press the middle switch in each group. I have a strong intuition that this is the most efficient algorithm for this case, but I don't know how to prove it, any hints?
4. I also suspect that the above algorithm is the most efficient for any ring of $n$ switches where $n$ is not a multiple of three, is this true? If so, how can I prove this?
5. Is there an established area of mathematics, in which this puzzle falls?

Answer 1

One approach is to prove that the $n$x$n$ matrix $$M_n = \begin{bmatrix} 1 & 1 & 0 & 0 & \dots & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & \dots & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & \dots & 0 & 0 & 0 \\ & & & & \vdots \\ 0 & 0 & 0 & 0 & \dots & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & \dots & 0 & 1 & 1 \\ \end{bmatrix}$$

has a nonzero determinant (it's actually $\pm 3$) for $n\not\equiv 0 \pmod 3$. Then there is only 1 unique solution to this problem (given by the matrix inverse $\pmod 2$) and so it must be minimum.

If $3|n$ then $$\sum_{k\equiv 0 \pmod 3} M_{\text{Row }k} = \sum_{k\equiv 1 \pmod 3} M_{\text{Row }k} = \sum_{k\equiv 2 \pmod 3} M_{\text{Row }k} = \begin{bmatrix} 1& 1 & \dots &1\end{bmatrix}$$

so the rows are not linearly independent so the determinant is zero.

Prove inductively that the determinant of a tridiagonal binary matrix of order $n$ is: $$\det(\text{Tri}_n) = \det(\text{Tri}_{n-1}) - \det(\text{Tri}_{n-2}) = \begin{cases} n\equiv 0 \pmod 6 & : 1 \\ n\equiv 1 \pmod 6 & : 1 \\ n\equiv 2 \pmod 6 & : 0 \\ n\equiv 3 \pmod 6 & : -1 \\ n\equiv 4 \pmod 6 & : -1 \\ n\equiv 5 \pmod 6 & : 0 \\ \end{cases}$$

Then use multilinearity of the determinant on the first and last column of $M$ to write $\det (M)$ in terms of smaller tridiagonal binary matrices show $\det (M_n) = 0 \iff n \equiv 0 \pmod 3$.

Answer 2

You can think of this as a problem in $F_2^n$, the $n$-dimensional vector space over the field of 2 elements $\{0, 1\}$. A vector in that space isa list of $n$ ones and zeros, so it corresponds to a set of lights being on or off; I'll call that a "state".

You also have a way to change state: you can flip switch 2, which changes the state of lamps 1, 2, and 3. So it corresponds to adding the vector

$$ v_2 = (1,1,1,0,0,...,0) $$

to the current state (with addition mod 2, of course). There's a similar vector for each switch you can flip; for switch 3, it's $$ v_3 = (0,1,1,1,0, ..., 0). $$

Clear?

You're asking "If we write $(1,1,..., 1)$ as a linear combination of the $v_i$, what's the smallest possible number of nonzero coefficients?

For $n$ a multiple of 3, it's easy: turn on switches 2, 5, 8, ..., 3(n-1) + 2, and you're done.

I believe that once you solve the problem for $n = 4, 5$, the solution for other $n$ will be pretty obvious as well. (essentially, any remaining groups of 3 don't really count for much...)

Answer 3

To get a light on, you have to either flip it once or three times and three times requires flipping three switches in a row. Flipping a switch twice never makes sense, as it does nothing. If you flip three switches in a row, the middle light will be on and the two next to it will be off, so you have to switch the two switches next to those three. This continues all the way around the circle.

For $n$ divisible by $3$, flip every third switch. Otherwise, you have to flip all the switches-there is no faster way.