[superprismatic]

N electric light bulbs numbered 1 to

N are arranged in a circle and are so

wired that pressing the switch to

turn on (off) any light also turns on

(off) the adjacent lights. At present

all lights are off and it is desired

to turn on only the first light. What

sequence of switches should be

activated? (Assume that N is not a

multiple of 3)

SUPERPRISMATIC CLARIFICATION: Pressing

the switch for light K will change the

state of lights K-1, K, and K+1 (mod N).

So, if those lights were (ON,ON,OFF)

then pressing that switch will change

it to (OFF,OFF,ON).

SUPERPRISMATIC'S QUESTION: Are there

any on-off patterns of lights which

are NOT achievable from the all off

condition using some sequence of

switch pushing?

SUPERPRISMATIC'S OTHER QUESTIONS:

Is it always possible to get from

any particular on-off pattern to

any other with some sequence of

switch pushing? Is this essentially

different than my previous question?

[Guest]

This one is going to be fun, SP.

[bushindo]

N electric light bulbs numbered 1 to

N are arranged in a circle and are so

wired that pressing the switch to

turn on (off) any light also turns on

(off) the adjacent lights. At present

all lights are off and it is desired

to turn on only the first light. What

sequence of switches should be

activated? (Assume that N is not a

multiple of 3)

Do you mean that assume N is not equal to 3*n + 1, for some integer n? Because

it is easy to show that we can turn 1 light on from an all off-position, if N = 3n + 1. And if we can turn 1 light on, we can turn another one on without changing the existing state of the other n-1 lights. That means we can reach all of the 2^N states from any other state.

For the general case, we have 2^N possible states. It only matters if we push any particular switch 0 or 1 times, because pushing a switch an even number of times is equivalent to pushing it zero times. Likewise, pushing a switch an odd number of time is equivalent to pushing the switch 1 time. So, there are 2^N permutations of switch we can hit. For some N, if we can prove that two permutations of switching can result in the same configuration of lights, then there is no way to turn a single arbitrary light on from all an all-off configuration.

Edited August 12, 2009 by bushindo

[Guest]

I did this with 7 lights in a circle numbered sequentially 1 -7, 7 being next to 1, I also assumed all the lights were off before I started, else, with this sequence, they would all be lit except the #1 light.

2,5,7,6,7,3

[bushindo]

Do you mean that assume N is not equal to 3*n + 1, for some integer n? Because

it is easy to show that we can turn 1 light on from an all off-position, if N = 3n + 1. And if we can turn 1 light on, we can turn another one on without changing the existing state of the other n-1 lights. That means we can reach all of the 2^N states from any other state.

For the general case, we have 2^N possible states. It only matters if we push any particular switch 0 or 1 times, because pushing a switch an even number of times is equivalent to pushing it zero times. Likewise, pushing a switch an odd number of time is equivalent to pushing the switch 1 time. So, there are 2^N permutations of switch we can hit. For some N, if we can prove that two permutations of switching can result in the same configuration of lights, then there is no way to turn a single arbitrary light on from all an all-off configuration.

I did some more work, ignore the above thought. Answers for the above.

So it seems that we can not turn a single light on for N being a multiple of 3. We can think of this as a matrix system,

mod( Ax, 2) = y

where A is a matrix of 0 with 1's on the diagonal and immediately to the left and rights of the diagonals. x is a binary vector of length N indicating which switch are on, and y is a binary vector of length N indicating which lights are on. The x vector is binary because it only matters if we push any particular switch 0 or 1 times. Pushing a switch an even number of times is equivalent to pushing it zero times. Likewise, pushing a switch an odd number of time is equivalent to pushing the switch 1 time. The output space has 2^N states, as does the input space. Therefore A has to be full-ranked. That is, A is 1-to-1. For N being a multiple of 3, we can show that we can find two switch configurations such that they lead to the same light-configuration. Therefore, A is not 1-to-1, there exist some light configuration states that are not reachable from the switch-configuration space.

For N not being a multiple of 3

Claim: if we can turn an arbitrary single light on from an all-off state, we can reach all of the 2^n states from every other state.

Proof: being able to turn the i-th light on means that there is a switch-configuration that will flip the i-th switch an odd number of times, and the other N-1 switches an even number of times. Since the system is symmetric and does not favor any particular switch, if we can turn only the i-th switch alone, then we can modify the switch-configuration so that we can turn any other light on alone.

Assuming that we can turn a single light on, doing that does not change the existing light-status for the other N-1 states, since the process flips the other N-1 states an even number of times. Therefore, we can easily construct all 2^N states.

To be complete, we need to show that for N not being a multiple of 3, there is a particular configuration of switch-flips that will turn only 1 light on. I have worked out the first couple of cases, but don't have a complete general proof yet. I have dinner now, so I'll get back to that later.

Edited August 12, 2009 by bushindo

[Guest]

If N is congruent to 1 modulo 3, then flip the switches whose number is not evenly divisible by 3. First, note that any light that is evenly divisible by 3 is off since the switch labelled one less than it and the switch labelled one more than it have been flipped, which turns the light on and then off. Also, any light between 1 and N that is not evenly divisible by 3 was flipped on and had precisely one neighbor next to it that was flipped as well, turning the light off. Finally, we need to consider 1 and N. Since N=3k+1, that means that N-1=3k and so it was not a flipped switch, thus not affecting light N. Furthermore, switch N was flipped on and switch 1 was flipped on as well, turning light N off. Lastly, switches 1, 2 and N were all flipped and are the only possible switches that affect light 1. No matter the order that they're flipped, it's clear that flipping a light on/off an odd number of times will turn the light on. Thus, light 1 will remain on, while the rest are off.

If N is congruent to 2 modulo 3, then flip all the switches except those labelled with a number that is congruent to 2 modulo 3. Again, lights 2 through N-1 are will be easy to see to remain off (like above) and only lights N and 1 are possibly a challenge. Switch N=3j+2 was not flipped, while switch N-1=3j+1 was flipped and switch 1 was not flipped. Thus, light N (which is only affected by switches N-1, N and 1) was flipped twice, turning it on and then off. Lastly, light 1 is affected by switches 1, 2 and N. Note that both switches 2 and N are congruent to 2 modulo 3, so they were not flipped, while switch 1 was flipped. Hence, light 1 was flipped on.

As for the other questions, I agree with Bushindo's latest post.