You have seven light bulbs in a circle. All the lights are off and you want to turn them all on. You are allowed to switch the state of any three adjacent light bulbs at time. What is the minimum number of steps you will need to turn them all on?

Just to illustrate, this is an example of what you can do. 0 means that the light is off. 1 means that the light is on.

Step - State

0th - 0 0 0 0 0 0 0

1st - 1 1 1 0 0 0 0

2nd - 1 1 0 1 1 0 0

3rd - 0 0 0 1 1 0 1 ...

If you are feeling brave enough, try to generalize it to N light bulbs in a circle, switching M at a time.

  • $\begingroup$ @MikeEarnest not an exact duplicate of that question, M is a variable here. $\endgroup$ – Jasen Dec 19 '17 at 1:59

The solution is to

Switch each light once (so 7 steps), no matter in what order. Because of the uneven number of lights and the fact that they are in a circle, this means every light's state will be changed an uneven number of times, AKA from off to on or from 0 to 1.

Also, that would make the formula:

N = M

  • $\begingroup$ the question asked how many steps, you should include that information in the answer. $\endgroup$ – Jasen Dec 19 '17 at 1:56
  • $\begingroup$ the general answer is N/GCD(M,N) $\endgroup$ – Jasen Dec 19 '17 at 2:01

Not the answer you're looking for? Browse other questions tagged or ask your own question.