Turn off all lights in a ring-shaped palace

Question

Not a very difficult question, but one I enjoyed nonetheless and wanted to share with the community.

You are a servant in a palace. The palace is in the shape of a circle, and you do not know how many rooms there are in the palace.

Some of the rooms have the lights on, some have the lights off. Your job is to turn all the lights off. I remind you again that the palace is ring shaped, and you do not know how many rooms there are in the palace.

How would you turn off all the lights, and in the end inform your superior (via your cell phone) that you have completed your job?

Notes:

• It's not something stupid like "touch the light bulb to see if its warm" or anything like that.
• You are not allowed to leave any distinguishing objects or markers to notify you where you've been. (I already heard solutions like "leave your clothes at room 0 and now just close all the lights naked".)

Answer 1

Setup: If you are in the room with lights off, turn them on. If lights are on, leave them on.

Iteration: Go counterclockwise counting rooms as you pass them, until you find a room with lights on (because of setup action, you are guaranteed to find one). Turn lights off. Return to the initial room (according to the count). Check the state of lights. If lights are off, you just made the full circle, and you are done. Otherwise, keep iterating.

The algorithm has a quadratic time complexity; I have no idea if there is a faster one.

Answer 2

One possible algorithm has just three state data: Integers $k$ and $n$, and a Boolean $f$. Start in any room, with $k = 0$, $n=0$, and $f$ true. (The meaning of $f$ is "I am currently moving in the 'forward' direction". The meaning of $k$ will be a forward room number.)

Turn on the light in that first room. Then:

• If $f$ is false and $k=0$ and the light is off in the room you are in, then the algorithm completes; you know all lights are off. (You may or may not end up in the starting room.)
• If $f$ is false and $k > 0$ then the light in your room will be off; leave it off, move in the backward direction to the next room, and decrease $k$ by one.
• If $f$ is false and $k=0$ and the light is on, then you are in the starting room; increase $n$ by one, set $f$ true to start moving forward.
• If $f$ is true and $k < 2^n$ move forward by one room, and turn off the light in the new room (which may, unbeknownst to you, actually be the starting room).
• If $f$ is true and $k = 2^n$, turn $f$ to flase, to start moving back toward the starting room to check if the light there is still on.

This algorithm turns off the lights with 100% certainty, and for $R$ rooms concludes in at most $$2^{2+\left\lceil \log_2 R\right\rceil} -2 $$ steps. This is always less than $8R$ steps.

Summary

Turn the light on in your room. Go 1 clockwise. If on, turn off along the way. Go back to starting room. If starting room light is on, go 2 counterclockwise. If on, turn off along the way. Go back to the starting room. If on, go 4 clockwise, etc. When the starting room light is off upon returning, you're done.

I'm not sure if you can do better; I suspect you can by using increasing sweeps of a factor of $e$ rather than a factor of $2$ each time.

Answer 3

I prefer the keep it simple method.

• Leave the light on at your starting room
• Turn off the lights to either side, if necessary.

Now the simple alternating algorithm:

• Move along to the right, counting each room as you pass, until you get to a light that is on. Turn it off.
• Turn around and count back down the number of rooms you moved. Now you know you're back at your starting room.
• If the light is on, you proceed to repeat the procedure in the opposite direction.
• If the light is off, you know you've gone around the entire circle and turned off the light in your starting room, then gone BACK around the entire circle to realize you turned off your starting room's light.

Et voila.

Answer 4

Step 1 - Find the fuse box and cut all electricity to the palace thus turning off all the lights.

Step 2 - Tell your supervisor.

Step 3 - Be sacked for gross misconduct.

Hurrah!

Answer 5

Here's a finite-state algorithm, in case there are too many rooms for you to count.

1. Turn the light off; go clockwise; turn the light on; go clockwise; turn the light on; go clockwise; turn the light off; go clockwise. (This pattern of lights is your "start marker".)
2. Turn the light off and go clockwise. Unless this is the second room in a row you've encountered that had the lights on when you arrived, repeat this step. (We might have turned off one of the lights in the start marker.)
3. Go counter-clockwise until you encounter a room with the lights on. (This must be the second "on" light of the start marker.)
4. Go counter-clockwise. If the light is off, then go clockwise, turn the light off, and finish. Otherwise, continue. (Since the light which was on is now off, we've made a full circle and we're done.)
5. Go clockwise twice and return to step 2. (The start marker is still intact, so we have to continue.)

This algorithm should work as long as there are at least three rooms.

Answer 6

The best answers (fitting the strategy and reachability tags) use a sentinel room (e.g. user58697's answer).

However, if you can rely on the path being a perfect circle (and not merely circular), there is also a geometric solution.

Place both ends of a ruler of unit length against the circle and measure the arc length (call it $a$), then derive the radius of the circle from $1/(2r) = \sin (\theta/2)$ (right triangle from half the ruler to the circle centre) and $a = r \theta$ (formula for arc length), where $r$ is the radius of the circle and $\theta$ is the angle subtended at the centre of the circle by the arc.

With the radius, you can calculate the circumference of the circle. Walk this length and turn off all lights as you go, then call the boss.

Answer 7

Since we're not allowed to touch light bulbs, I guess we're not allowed to use a map, a compass or (welcome to the 21st century) GPS either. :-)

I'm assuming that I walk room-to-room around the ring, with switches at clockwise and counter-clockwise doors, and I'm refusing to walk through a room in the dark (for safety). Basically I'm going to turn lights on as I walk away from my start room, then turn them off as I return.

So. I start in room $0$ with the lights on, and choose my initial direction. First action though is in the opposite direction: I turn on the lights in the adjacent opposite-direction room (if necessary). Then I head in my chosen direection, turn off room 0 lights as I leave, and turning on the lights in room 1 if necessary.

Now I proceed until I find a single room with lights off - that is, where the rooms before and after are lit. Call this room $n_1$. Now I'll proceed further (of course turning on the lights in room $n_1$) to room $2n_1$. If I find any dark rooms, I discard the existing value of $n_1$ and keep looking for a new single dark room. (If the new dark room I found was a single dark room, it becomes the new $n_1$). Keep going until I have walked though already-lit rooms from $n_1$ to $2n_1$.

Now I head back to room $0$, leaving the light in $2n_1$ on but otherwise turning off lights as I go. If I reach room $n_1$ and the following light is off, it was also room $0$ and all the lights are off. Otherwise, on reaching room $0$, I cross over and start out in the opposite direction, turning on lights as I go (after room $0$, which is left dark). Now I am looking for a sequence of exactly $2n_1$ rooms that are dark. I proceed as before, calling the last room in the $2n_1$ dark-room sequence room $n_2$ and continuing through another $n_2$ lit rooms to room $2n_2$ (or continuing the search for $n_2$ if any dark rooms are found). Then I head back to room $0$, leaving the last room light on and otherwise turning lights off.

I continue iterating in opposite directions until I find an already-dark room on the way back to room $0$. The lights are then off.

By my reckoning I should walk through $kR$ rooms, where $R$ is the total number of rooms and $k$ is between $3$ and $4$.

Answer 8

At last Peter has found a new job as servant in a palace. But it was a strange palace; all rooms looked alike and you never knew where you are. It was maddening. And the older servants weren't a help. All the unpleasant tasks were loaded onto him. His newest task was to turn off all the lights in this looping, never ending palace.

Before he started he set $i=1$
#START#
He went through $2^{i-1}$ rooms and switched all the lights in there off.
At the last room he stopped, turned around and switched the lights on to help him thinking.
He just switched off the lights in $2^{i-1}$ rooms and checked that the lights in the $2^{i-1}-1$ before those were switched off too.
That means he knew the light in the last $2^i-1$ rooms are already turned off.
But better save than sorry he checked the $2^i-1$ rooms.
The first few times he didn't find any turned on lights and he increased i by one and repeated the steps from the #START# without turning around.

When he found a light switched on something inside him just snapped. A light that he knew was turned off was turned on again. And all those equal looking rooms. Nothing ever changing. Repeating forever ... He switched the light off and escaped the palace and committed himself in a loony bin.

The next day when the other servants came they checked and found that all lights were switched off.

Why does this algorithm works:

In the 1st loop he turns $1$ light off and has $0$ already turned off. Making a total of $1$ light off that he checks.
In the 2nd loop he turns $2$ light off and has $1$ already turned off. Making a total of $3$ light off that he checks.
In the 3rd loop he turns $4$ light off and has $3$ already turned off. Making a total of $7$ light off that he checks.
...
In the i-th loop he turns $2^{i-1}$ lights off and has $2^{i-1}-1$ already turned off. Making a total of $2^i-1$ light off.

Lets look at the k-th loop with $k=\lceil log_2(R+1)\rceil$.
At the end of the loop he checks $2^k-1\geq R$ rooms. That means he checks all rooms. Before checking he turns the lights in one room on the check fails after he runs once through the whole palace. That light is the only one that is on. He shut it off and is finished.

How much does the servant moves:

In the 1st loop he moves 1 time to turn lights off. 1 time to turn one light on and 1 time to check them. 3 times in total.
In the 2nd loop he moves 2 time to turn lights off. 1 time to turn one light on and 3 time to check them. 6 times in total. Together with the previous loop 9 times total.
In the 3rd loop he moves 4 time to turn lights off. 1 time to turn one light on and 7 time to check them. 12 times in total. Together with the previous loops 21 times total.
...
In the i-th loop he moves $2^{i-1}$ time to turn lights off. 1 time to turn one light on and $2^i-1$ time to check them. $3*2^{i-1}$ times in total. Together with the previous loops $3*2^i-3$ times total.

In the k-th loop he moves $2^{k-1}$ time to turn lights off. 1 time to turn one light on and R times to check them.

In total we have k-1 full loops plus the last loop: $3*2^{k-1}-3+2^{k-1}+1+R = 4*2^{k-1}+R-2 = 4*2^{\lceil log_2(R+1)\rceil-1}+R-2 \\= 4*2^{\lfloor log_2(R)\rfloor+1-1}+R-2 \leq 4*R+R-2 = 5*R-2$

Result: He has to move up to $5*R-2$ times.

This can be improved by 1 step by not starting with a move and maybe by using an other base.

Answer 9

As Tanner Swett has noted, it's possible to solve the puzzle using a finite number of states beyond those of the lights themselves. His solution takes time proportional to the square of the number of lights [i.e. O(N^2); I think that may be improved to time proportional to O(NlgN) at the expense of using an increased number of states, using the approach described below. For simplicity, light bulbs will be considered in pairs and certain aspects of the algorithm will be simplified. I'll regard the value of each pair of lights as being 0, 1, or 3, with zero being both lights on and 3 being both lights off.

1. Start by establishing a state of 222203 [confirm that there are at least enough lights for that] with the person standing at the zero.

2. Working left to right, copy everything one place to the right until one encounters a 3, making note of whether one saw any zeroes. Copy the three one place to the right from where it started.

3. If one saw any zeroes, then travel right to left until one reaches a 2; flip bits up to and including the first "1" one encounters. Then go back to step 2.

4. Using basically the reverse of the logic in steps 2-3, "march" right to left, leaving behind a trail of threes.

5. Check whether the value the last two that was copied is are 2. If they are, then write another few 2s to their left, replace the rightmost two of the bunch with a zero, and go back to step 2.

6. If the value just beyond the last 2 that was recently copied isn't 2, things have wrapped. Proceed rightward writing 3s until a 3 is reached, whereupon everything will be 3 (meaning all lights are off).

Each of the above steps would require a few states to implement, so the overall number of states would be large enough to make enumeration irksome, but conceptually not difficult. I think describing things in terms of "steps" is clearer than states, however.

Answer 10

First stand in the corridor and look left and right and count how many rooms you can see and call that X. Then let's just guess that the number of rooms is about Y times that number. What Y exactly is I can't say now - it all depends on width of the corridor and other factors - but I would say that any person that would come up with a mathematical algorithm to solve this question can also make some pretty accurate estimations about this. And to be sure just take twice that number so you'll go through 2 * X * Y rooms. I can't possibly imagine you won't get it that way and this way you will open less than 2 * R rooms where R is the number of rooms.

Answer 11

The servant could also use a geometric pattern of on/off that would be unlikely to occur as a marker of where he/she started. This wouldn't reduce the probability of leaving a light on to zero, but it could reduce it to an arbitrarily low value depending on the length and complexity of the pattern. Realistically (for a human), this may be more reliable because it may be easier to remember the rules behind a geometric pattern than it would be to be sure of a room count if the total number of rooms was very large (I know with ~500 rooms I would loose count several times and doubt my count even if I didn't actually miscount).

Answer 12

- My solution :

• turn on light in actual room and adjacent one (that is because we dont know if number of rooms is odd or even)

• turn off light in third room , and on in fourth room , off in 5th ....alternatively , count all rooms passed through until:

  • until coming across two lighted rooms that precedes a succession of switched on , off lights then stop counting , and remind it .

• turn off two successive lights and go way round , turn off all lights of n rooms crossed over, if you end up with two switched off lights it means you have just achieved your task , otherwise , someone is playing around with you, and you should repeat the task from the room n° n+1