[Math] Lightbulb puzzle related to proofs by induction.

inductionpuzzle

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?

Best Answer

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

Related Question