71
$\begingroup$

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".)
$\endgroup$

migrated from math.stackexchange.com Mar 12 '15 at 12:13

This question came from our site for people studying math at any level and professionals in related fields.

  • 24
    $\begingroup$ Perhaps you should rephrase, along these lines: "Your job is to shut off all the lights and then report to the boss when you've finished; naturally, the boss will kill you if you've lied. The boss is also impatient, so finish as quickly as possible." Otherwise, a perfectly legitimate answer would be: Walk from room to room, turning off every on-light you encounter; in number-of-room steps, you'll be done although you won't realize it. There's nothing in the problem statement that says you can't just keep walking obliviously through the completely-darkened ring forever. $\endgroup$ – Blue Mar 11 '15 at 20:26
  • 9
    $\begingroup$ I agree with @Blue. Until I read his comment, I truly didn't understand why "just walk the circle and turn the lights off (see also: How many mathematicians does it take to turn off a light bulb??)" wouldn't have worked. We need to know when we're done, got it. $\endgroup$ – pjs36 Mar 11 '15 at 22:31
  • 4
    $\begingroup$ Do the rooms have windows/skylights/external doors? Do they have features or layouts which distinguish them from one another? Am I allowed to use a compass? A GPS? Radio direction-finding? Are there other people in the palace and if so once I've switched a light off can they switch it back on again? $\endgroup$ – A E Mar 12 '15 at 10:59
  • 3
    $\begingroup$ @AE - I'm thinking that actually this is Satan's palace, and you've just been promoted from wallowing in molten sulphur to assistant lightswitch flunky. Don't expect any technological assistance, and the penalty of failure will not be slight. $\endgroup$ – Joffan Mar 12 '15 at 17:01
  • 6
    $\begingroup$ It seems like it is feasible to determine the Radius of the Palace using some Trig and basic step measurements. From this you can get a good estimate on the number of rooms. Add 50% for safety and do it in about 1.5 passes. $\endgroup$ – kadreal Mar 12 '15 at 22:50

12 Answers 12

52
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ More efficient, I think may be when you get to a room with a light on (including initial room) switch it off, and go to the next room in the direction you are going. If the light there is on, switch it off, and continue - and do the same until you get to a room with the light out. Switch that light on and change direction. You can count rooms to know when to turn the last light out. If all lights are on, for example, this is better. $\endgroup$ – Mark Bennet Mar 11 '15 at 20:10
  • $\begingroup$ How do you know when you're done with the setup? $\endgroup$ – Scott Caldwell Mar 11 '15 at 20:12
  • $\begingroup$ I have an algorithm with linear time complexity; see answer below. $\endgroup$ – Mark Fischler Mar 11 '15 at 20:17
  • 1
    $\begingroup$ @ScottCaldwell Setup is a one-time thing. It only concerns the initial room: make sure that lights there are on before you start iterating. $\endgroup$ – user58697 Mar 11 '15 at 20:17
  • $\begingroup$ Ohhh, I see. Not bad. $\endgroup$ – Scott Caldwell Mar 11 '15 at 20:19
35
$\begingroup$

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.

$\endgroup$
  • 24
    $\begingroup$ This is the best answer so far. To summarize: 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. $\endgroup$ – Tim Clark Mar 11 '15 at 20:44
  • 1
    $\begingroup$ And to explain the time complexity of the algorithm: Assume for simplicity that R is a power of 2. Then each "sweep" of size $2^{i}$ takes $2*2^{i}$ because we have to go out and back. So it takes $2*(1 + 2 + ... + R) = 2\sum\limits_{i = 0}^{log_{2}R}2^{i} = 2(2^{log_{2}R + 1} - 1) = (2^{log_{2}R + 2} - 2)$ This is equal to 4R - 2. Non power of 2 values of R require the ceiling function, as described in the answer. When R is non-power of two it bumps up to 8R - 2. That was a well thought out answer, Mark! $\endgroup$ – Tim Clark Mar 12 '15 at 0:16
  • $\begingroup$ Thank you. Various "rooms and switches" problems become very tough and/or interesting if you care about efficiency of the solution. $\endgroup$ – Mark Fischler Mar 12 '15 at 0:36
  • 1
    $\begingroup$ How about turning off lights clockwise till to come to a dark room. Return to the starting room, if dark then you are done. If not turn off lights counter clockwise till you come to a dark room. Return to the starting room an repeat till the starting room is dark. $\endgroup$ – aggsol Mar 12 '15 at 12:19
  • $\begingroup$ @CodeClown Doesn't work if the starting room is off and the second room is off, but there are more than 2 rooms. By your strategy, you'd go to the second room (clockwise) see it is off, return to the start and see it is off and claim you are done. You haven't checked rooms three or higher and they could still be on. $\endgroup$ – Trenin Mar 12 '15 at 17:09
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Mark beat you to it. $\endgroup$ – Dodgie Mar 12 '15 at 0:28
  • $\begingroup$ This method is OK, but what exactly is the purpose of alternating directions? I can conceive it might be give a smaller time in some cases, but the question does not ask for efficiency. And if it did, a better option would seem to be to at each point choose that direction for which (based on history) you will be in unknown territory most quickly. $\endgroup$ – Marc van Leeuwen Mar 12 '15 at 9:39
  • 1
    $\begingroup$ You could turn off multiple lights in one go. $\endgroup$ – aggsol Mar 12 '15 at 12:22
  • 1
    $\begingroup$ @MarcvanLeeuwan "the direction for which you will be in unknown territory most quickly" is the opposite direction to the last one you checked (so you alternate). $\endgroup$ – user253751 Mar 13 '15 at 9:09
10
$\begingroup$

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!

$\endgroup$
  • 3
    $\begingroup$ I just wanted to clarify that this question isn't looking for creative or out-of-the-box answers, as it is a puzzle in logic. Hopefully this clears up any misunderstandings! $\endgroup$ – Aza Mar 12 '15 at 16:09
  • 3
    $\begingroup$ This kind of solution (a joke answer to a pure logic puzzle) is frowned upon here, and would generally fit better as a comment (unless it's really funny). $\endgroup$ – Lopsy Mar 12 '15 at 17:11
  • 5
    $\begingroup$ @Mazura Hire a building company to remove the roof. (O(1) time for you, at least O(n) for the builders) Alternatively, connect up a transformer so that the building's power is several times the normal voltage, and the lightbulbs catch fire somehow. $\endgroup$ – user253751 Mar 13 '15 at 9:10
  • 3
    $\begingroup$ I like this solution (if OP wanted to present this as a pure-maths problem then they could have done - if we're in a palace then we're in a palace). An alternative (without leaving the room) would be to use the light-bulb connection to fuse the circuit / trip the breaker. $\endgroup$ – A E Mar 13 '15 at 13:03
  • 3
    $\begingroup$ Calculating the volume of a light blub is stupid, submerging it in water and noting its displacement is smart. $\endgroup$ – Mazura Mar 15 '15 at 22:35
8
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Any "start marker" you could possibly pick could occur by chance, therefore it isn't a reliable signal of completion. However, you might be able to make a hybrid between this and other methods presented here so that you don't bother checking when the marking set of light patterns is not found. However, you have to be careful about the size of your pattern vs. the size of the palace--if your pattern is 10 long and the palace is 8 rooms, you're going to have a problem. $\endgroup$ – ErikE Mar 12 '15 at 20:55
  • 2
    $\begingroup$ @ErikE This solution doesn't depend on the uniqueness of the start marker; it'll still work even if the start marker appears by coincidence several times. This is because every time the servant finds a pattern of lights that looks like the start marker, they go back to the real start marker and see whether or not it's been altered. If it has been altered, they've made a full circle; if it hasn't been altered, they need to continue. $\endgroup$ – Tanner Swett Mar 12 '15 at 22:15
  • 1
    $\begingroup$ @TannerSwett: Your answer inspired me to work out an improvement. I think yours is time O(N^2); mine is O(NlgN). Yours, however, requires many fewer states. $\endgroup$ – supercat Mar 13 '15 at 2:51
  • $\begingroup$ @TannerSwett Clearly I wasn't paying attention because the solution I suggested is the one you already presented! Haha :) $\endgroup$ – ErikE Mar 13 '15 at 17:38
  • $\begingroup$ +1 for finite state solution. Solutions with counting are not only theoretically unsound for an unbounded number of rooms, but practically unsound since most people can't reliably keep track of such huge numbers over and over. :-) $\endgroup$ – R.. Mar 14 '15 at 13:56
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I like the concept but it doesn't work in practice for large numbers of rooms. The precision requirements of the measurement grow with the number of rooms, so you would need measuring devices whose precisions magically tune to the scale of the problem. $\endgroup$ – R.. Mar 14 '15 at 13:58
  • 1
    $\begingroup$ @R.. Ah, but in practice, you couldn't rely on the structure being perfectly circular, which is why the best answers use sentinels. :) Wikipedia suggests Ak Saray is the largest palace in the world, with 289,000 m^2 of floor area. A circular palace of that area can have 300m radius after taking into account room depth. A 1.5m corridor allows about 10cm difference between the chord and arc length over about a 60m arc length. This is more than enough to allow a 1.1mm/10m error <sola.at/1430_EN-Measure_of_length-Measuring_precision.htm>. Use the longest circumference within the error bounds. :) $\endgroup$ – Lawrence Mar 15 '15 at 7:31
  • $\begingroup$ Write down your initial GPS coordinates. Turn off all lights until reaching same coordinates again. $\endgroup$ – Cœur Nov 19 '17 at 10:42
  • 1
    $\begingroup$ @Cœur Haha - that works, too! $\endgroup$ – Lawrence Nov 19 '17 at 14:20
3
$\begingroup$

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

enter image description here
enter image description here
enter image description here

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ For large values of R, you're going to need really good eyes to be able to count the number of rooms as they vanish to a point (or worse yet, over the horizon). $\endgroup$ – R.. Mar 14 '15 at 14:03
  • $\begingroup$ Also serpentine hallway walls would totally defeat this strategy even for small values of R. $\endgroup$ – R.. Mar 14 '15 at 14:07
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Even a likely pattern can work here, i.e. two lit adjacent rooms to mark the start. The quadratic time algorithm by user58697 can then run without counting the rooms, but by checking if the pattern is still intact. (This produces only a linear overhead). The linear time algorithm by MarkFischler is incompatible with this approach. $\endgroup$ – Rolf Sievers Mar 12 '15 at 8:12
  • $\begingroup$ This also is pretty much equivalent to the algorithm given by Tanner Sweet. $\endgroup$ – Rolf Sievers Mar 12 '15 at 8:15
  • $\begingroup$ @Rolf Yes, I'd say that's exactly how my algorithm works. Mine uses "off, on, on, off" as a start marker, but now that I think about it, I think you're correct in saying that "on, on" would be sufficient. $\endgroup$ – Tanner Swett Mar 13 '15 at 3:28
-1
$\begingroup$

- 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

$\endgroup$