## Light Switches!

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

Vossy
Posts: 11
Joined: Fri Dec 26, 2008 2:20 pm UTC
Location: Brisbane, Australia

### Light Switches!

I have a system of 'n' light switches and 'n' light bulbs arranged in a single row with each light bulb directly above a switch. When I flick a light switch, the light directly above that switch AND both lights on either side are toggled (ie, if a light was on, it is now off). Note that the first and last switch will only toggle 2 bulbs.

The problem is this: For what values of 'n' is the system completely solvable? By this I mean, given ANY starting configuration of light bulbs on and off, what number of switches guarantees that I can turn all the light bulbs off?

Example: For n=1, the system is solvable. There is a single bulb and a single switch. If the bulb is on, flick the switch. If the bulb is off, don't flick it.

For n=2, the system is not solvable. Flicking either the left or the right switch will toggle both bulbs, so from the initial configuration (off, on), there is no solution.

For n=3, the system is solvable. I'll leave you to figure out why - the logic is similar to above.

For what values of 'n' does it not matter what bulbs are on to begin with? Points for getting the correct "rule" for n, but the real trick is proving it!

SlyReaper
inflatable
Posts: 8015
Joined: Mon Dec 31, 2007 11:09 pm UTC
Location: Bristol, Old Blighty

### Re: Light Switches!

This must have something to do with being able to change the end bulbs independantly of the others. Without loss of generality, assume all bulbs start in the off state, and we want to be able to toggle bulbs independantly of each other through some sequence of switch flicks (this is equivalent to the stated problem). A central bulb can by switched on, and all surrounding bulbs switched off quite easily. You'd be able to move the bulbs which are switched on outwards to the edges by flicking switches in the right order:

Let o be an off bulb, x be an on one

Code: Select all

1. ...oooooooooooooooooooooooooooo...2. ...ooooooooooxxxooooooooooooooo...3. ...ooooooooxxoxoxxooooooooooooo...4. ...oooooooxoooxoooxoooooooooooo...5. ...oooooxxooooxooooxxoooooooooo...

So you see, the on bulbs can be pushed outward towards the edges, and it will either be a single on bulbs at the edge or a pair of on bulbs at the edge.

So the problem is what happens at the edges. Obviously if you have two on bulbs at the edge, these can be switched off by flicking the end switch. If it's just the very end lit up, I can see no way to solve it without creating lit bulbs again back towards the center.

I'm going to guess it can only be done for cases n = 1, n = 3. Because those are the only cases where one end can directly affect the bulbs at the other end, which gives us a way to resolve the "one lit bulb at the very end" problem.

I'm almost certainly wrong, of course.

What would Baron Harkonnen do?

Macbi
Posts: 941
Joined: Mon Apr 09, 2007 8:32 am UTC
Location: UKvia

### Re: Light Switches!

Spoiler:
Every n not 2 mod 3.
Number the Lights 1 to n.

Obviously if we have a way to light a set of Lights from having all of them blank, we can toggle that set when we want.

Lemma 1: Light 3 can be toggled.
Proof: Switch 1 then Switch 2.

Lemma 2: If we can toggle a Light we can toggle one 3 away.
Proof: if we want to toggle k+3 then we hit Switch k+2 and then Switch k+1 and then toggle Light k. Similar for Light k-3.

Theorem 1: All Lights can be individually toggled if n=0 or 1 mod 3.
Proof:If n=0 mod 3, then using Lemma 2 we can work along from Light 3 (which we can toggle by Lemma 1) showing that we can toggle each Light that divides by 3. This shows we can toggle Light n. Hitting Switch n and then toggling n has the effect of toggling Light n-1. We can then work back (Lemma 2) showing we can toggle each Light that is 2 mod 3. Hitting Switch 1 and toggling Light 2 lets us toggle Light 1, and then we can toggle all the 1 mod 3 Lights (Lemma 2 again).
(at this point the word "toggle" has lost all meaning to me)
Similarly if n=1 mod 3, then we can toggle the 0 mod 3's including n-1. So switching n and toggling n-1 toggles Light n, giving us all the 1 mod 3's, including Light 1. Then toggling 1 and hitting Switch 1 toggles Light 2, so we have all the 2 mod 3's as well. Q.E.D.

Theorem: If n = 2 mod 3 then Lights that are not 0 mod 3 cannot be individually toggled.
Proof:Each of the Switches apart from 1 and n changes a Light that is 0 mod 3. So if we had a method to toggle Lights that are not 0 mod 3, it would have to use an even amount of these moves. But the Switches on the ends toggle an even amount of Lights, so the total amount of Lights change would be even, so a single Light can't be toggled as the end result. Q.E.D.

And we're done...
(Proving Theorem 2 was fun, even if Theorem 1 wasn't. Anyone have a nice proof of Theorem 1?)
Indigo is a lie.
Which idiot decided that websites can't go within 4cm of the edge of the screen?
There should be a null word, for the question "Is anybody there?" and to see if microphones are on.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Light Switches!

Spoiler:
Given a desired output, the first 2 switches uniquely determine the rest (since the 2nd light is now only modified by the 3rd switch, and once that's determined, the 3rd is only modified by the 4th, and so on).

Since the number of switch positions equals the number of light positions, it's completely solvable whenever there is no 'do nothing' move other than doing nothing. The only non-trivial move that does nothing to the first light is the move starting by toggling the first 2 switches, and if the desired output is no change, this sequence must continue as 110110110110110... (where 1 represents a toggle and 0 represents doing nothing). Truncating this leaves the last light alone if and only if the last two moves were 11 or 00. So there are 'do nothing' moves for [imath]n \equiv 2 \mbox{ mod } 3[/imath]. Thus it's completely solvable for [imath]n \equiv 0, 1\mbox{ mod } 3[/imath]
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

imatrendytotebag
Posts: 152
Joined: Thu Nov 29, 2007 1:16 am UTC

### Re: Light Switches!

mike-l wrote:
Spoiler:
Given a desired output, the first 2 switches uniquely determine the rest (since the 2nd light is now only modified by the 3rd switch, and once that's determined, the 3rd is only modified by the 4th, and so on).

Since the number of switch positions equals the number of light positions, it's completely solvable whenever there is no 'do nothing' move other than doing nothing. The only non-trivial move that does nothing to the first light is the move starting by toggling the first 2 switches, and if the desired output is no change, this sequence must continue as 110110110110110... (where 1 represents a toggle and 0 represents doing nothing). Truncating this leaves the last light alone if and only if the last two moves were 11 or 00. So there are 'do nothing' moves for [imath]n \equiv 2 \mbox{ mod } 3[/imath]. Thus it's completely solvable for [imath]n \equiv 0, 1\mbox{ mod } 3[/imath]

Sweet! Or, another way to look at that same solution:

Spoiler:
We can think of the "switch space" S as an n-dimensional vector space over F2 (the field of two elements, or Z mod 2), where each coordinate that is a "1" is a switch that is flipped on, and the "light space" L an n-dimensional vector space over F2 where each coordinate that is a "1" is a light that is on. Then the map phi:S -> L that sends each switch to the lights that it turns on (ie, (1,0,0,0...) is sent to (1,1,0,0,...) and (0,1,0,...) is sent to (1,1,1,0,...) and (0,0,1,0,0,....) is sent to (0,1,1,1,0,...) etc.) is a linear map that sends each switch configuration to the corresponding light configuration. Then this problem is solvable iff phi is bijective iff phi is injective, or there are no nontrivial switch configurations that lead to trivial light configurations.

Now mike-I basically argued that the only possible nontrivial switch configurations are of the form 110110...11 when n = 2 mod 3, which is correct and solves the problem. Another solution path, using this viewpoint, would be to compute the determinant of the matrix of the linear transformation phi, for example:

$det\left(\begin{array}{ccccc}1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1\end{array}\right)$
(when n = 5) and the problem is solvable when the determinant is nonzero. In this case, I think mike-I's method is more elegant than the determinant computation, but this way generalizes easily to any way of making switches toggle certain lights.
Hey baby, I'm proving love at nth sight by induction and you're my base case.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

### Re: Light Switches!

imatrendytotebag wrote:Sweet! Or, another way to look at that same solution:

Spoiler:
We can think of the "switch space" S as an n-dimensional vector space over F2 (the field of two elements, or Z mod 2), where each coordinate that is a "1" is a switch that is flipped on, and the "light space" L an n-dimensional vector space over F2 where each coordinate that is a "1" is a light that is on. Then the map phi:S -> L that sends each switch to the lights that it turns on (ie, (1,0,0,0...) is sent to (1,1,0,0,...) and (0,1,0,...) is sent to (1,1,1,0,...) and (0,0,1,0,0,....) is sent to (0,1,1,1,0,...) etc.) is a linear map that sends each switch configuration to the corresponding light configuration. Then this problem is solvable iff phi is bijective iff phi is injective, or there are no nontrivial switch configurations that lead to trivial light configurations.

Now mike-I basically argued that the only possible nontrivial switch configurations are of the form 110110...11 when n = 2 mod 3, which is correct and solves the problem. Another solution path, using this viewpoint, would be to compute the determinant of the matrix of the linear transformation phi, for example:

$det\left(\begin{array}{ccccc}1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1\end{array}\right)$
(when n = 5) and the problem is solvable when the determinant is nonzero. In this case, I think mike-I's method is more elegant than the determinant computation, but this way generalizes easily to any way of making switches toggle certain lights.

That's pretty much exactly how I thought of it, I just
Spoiler:
calculated the kernel instead of taking the determinant
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.