wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> A Prisoner & 100 light bulbs
        
(Message started by: mattian on Jul 16^th, 2004, 9:50am)

Title: A Prisoner & 100 light bulbs
Post by mattian on Jul 16^th, 2004, 9:50am

Inspired by the now famous 100 prisoners problem, I have derived a new riddle. It actually doesn't relate to the original in any way except for the cast of characters - light bulbs, prisoners and cells.

Here is the riddle: (Please be aware of updates added to the end of this post)

-----------------------------------------------

A circular prison has its cells positioned uniformly around its circumference. Each cell has a light bulb. Each room also has a button which clicks each time it is depressed. Each button controls an arbitrary light bulb in one of the cells. For example, if the light bulb connected to a particular button is on and the button is pushed, that light bulb will go off, and vice versa.

A circular corridor lies on a circle just inside the circle of cells and there is a single door from the corridor into each cell.

A prison guard gives the sole prisoner some instructions and teleports him into the circular corridor to an arbitrary position. His instructions are to establish which buttons are connected to which bulbs and to declare it when he knows the complete solution in exchange for his freedom. The prisoner may make his declaration if and only if he knows the configuration of the button-bulb connections. His declaration will be made from within the corridor where he is able to reference doors in his solution.

The following facts apply:

1. The prisoner does not know how many cells there are in the prison.

2. The prisoner may visit the cells in any order.

3. The prisoner does not know the initial state of any of the bulbs.

4. The prisoner does not know any of the relationships between buttons and bulbs.

5. The switch may indeed be connected to the bulb in the same cell.

6. The relationships between buttons and bulbs are entirely random (white noise). There is no definable bias.

Question 1 - What strategy can the prisoner employ to guarantee his freedom?

Question 2 - How can the prisoner minimize the number of cell visits he needs to make before he can declare the solution?

Some wise-guy filters (disclaimers):

1. The buttons always work.
2. The bulbs burn entirely cold and will never burn out.
3. The prisoner cannot gain physical access to the bulbs in order to break them or damage them
4. Nothing that the prisoner does can have any effect on the prison except pressing a button in a cell which has only one outcome; a bulb somewhere in the prison comes on (or off).
5. The prison is pristine and exists in a perfect world where on means on and off means off and there is no inbetween.
6. The prisoner cannot beat up the guards.
7. The cells are entirely indistinguishable from each other in every respect other than the state of the light bulb - ON or OFF. There are no special markings, the prisoner doesn't have any crayons handy, no bloodstains may be left behind in any room.
8. Despite any efforts he might make, the prisoner can not extract any positional state information from the button - it always looks the same.
9. All operations on the button must be performed from within the respective cell with the door closed.
10. No information from the outside world will be available to the prisoner when he is inside a cell - the only information available to him from within the cell, is the state of the light bulb in that cell, and what he decides to do with the button (if anything).
11. To be set free, the prisoner must know the absolute solution and may not guess based on probabilities.
12. If you think you have an answer which solves the problem using some trivial "kill the guards, steal the key" solution which doesn't contradict any of the limitations of this puzzle, then this statement says you're wrong.
13. If your name is Nigel_Parsons, your solution is wrong.
14. Doors close automatically, and faster than the prisoner can move from one cell to another. There are no gaps around the door through which light can pass. From the corridor, the prisoner can see the state of only one bulb at a time - when he is entering or leaving a room. Observing the state of a bulb counts as a visit.

Addendum 1:
1a. I just realised that I should not have used "100" in the topic name as the number of cells (and therefore lightbulbs) is arbitrary in this problem.

Addendum 2:
2a. The prisoner does not have access to any measuring equipment.

2b. It is safe to assume that all cells may be visited in reasonable (finite) time. For the purpose of keeping this within scope, let us assume that the number of cells does not exceed 100 (and the prisoner knows this).

2c. It is also safe to assume the prisoner can travel to any cell in reasonable (finite) time, which implies that the area of the prison is also reasonably small and finite. Let us assume that the prison has a diameter no greater than 100 yds (300 ft).

2d. From within the corridor, the prisoner can see nothing but the corridor itself curving off and the doors to the cells on the outer wall.

Addendum 3:
3a. Please note new disclaimer additions #13 and #14.

3b. If this riddle is too long due to all the disclaimers then don't tell me, tell Nigel_Parsons ;-). (It's cool, Nigel, I'm just playing, keep sending your solutions!)

Addendum 4: (Compliments of Leonid Broukhis)

Quote:

4a. The prisoner does not have access to any measuring equipment, and he does not need any, because the width of the corridor happens to be equal to the distance between doors + the door width.

Title: Re: A Prisoner & 100 light bulbs
Post by rmsgrey on Jul 16^th, 2004, 11:27am

Some initial thoughts:

::[hide]
1) The prisoner cannot get any information from his first visit to a cell.

2) The only information potentially gained by toggling the bulb in a previously unvisited cell is that the switch doesn't control the light in any previously visited cell.

3) If the initial state is known, a binary approach will solve the problem with absolute certainty in O(n log n) visits to cells.

4) Due to the circular nature of the prison, determining the number of cells (assuming the prisoner can't measure the angle between successive cells or otherwise derive the number of cells - eg by tracking his orientation or by somehow recognising a specific cell) is going to be the meat of the problem, and will probably automatically solve most of the switch identification as well...
[/hide]::

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 16^th, 2004, 12:00pm

Note:
1. The prisoner does not have access to any measuring equipment.

2. It is safe to assume that all cells may be visited in reasonable (finite) time. For the purpose of keeping this within scope, let us assume that the number of cells does not exceed 1000 (and the prisoner knows this).

Responses to your initial comments.
::

1. Agreed.
2. Could you rephrase this statement making careful distinctions between toggling the button vs. toggling the bulb.
3. Agreed - although it should be noted that to switch any bulb on and observe it will require between 1 and 2 visits. I believe - using the most straight forward approach, given that the bulbs were all initially off - it would take closer to but not quite O(2n log n).
4. The prisoner does not have access to any measuring equipment. And yes - I believe that knowing the number of cells is a big piece of the puzzle.

::

Title: Re: A Prisoner & 100 light bulbs
Post by Leonid Broukhis on Jul 16^th, 2004, 4:59pm

Knowing the number of cells is easy:

::[hide]
Find a cell (X) in which a button controls some other cell.
S = bulb{X];
left = -1; rigth = -1; done = false;
For i = 1 step 1 until done do begin

if (left == -1) {
Go i cells to the left, press a button there.
Return to X
if S != bulb[X] then {
left = i;
if right != -1 then total = left + right; done = true
S = bulb[X]
}
}
if (right == -1) {
Go i cells to the right, press a button there
Return to X
if S != bulb[X] then {
right = i;
if left != -1 then total = left + right; done = true
S = bulb[X]
}
}
end for

[/hide]::

Using C notation to avoid visible math symbols

Title: Re: A Prisoner & 100 light bulbs
Post by Leonid Broukhis on Jul 16^th, 2004, 5:17pm

A big question is in what way should the prisoner explain the solution to the guard if there is no way for him to tell the cells apart? If there are no "fixed point" cells, there is no way to establish any frame of reference to explain a non-trivial solution. Suppose there are 5 cells:
A controls B, B controls D, D controls A
C controls E and vice versa.

Should then the solution be: "there are somewhere two cells separated by one cell that control one another (call them C and E). That cell between them (call it D) controls a cell one cell away to the left (call it A), which controls the only unnamed cell so far (call it B) which controls D"? BLECHH!

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 16^th, 2004, 6:54pm

Hey Leonid

First of all, while I agree that your method for determining how many cells there are will work, it isn't optimal. But, since I asked two questions in the riddle, first to establish a working strategy and then optimize, I will be satisfied with the first solution first and the second second.

Secondly, to answer your question. If the prisoner correctly establishes the number of cells, it is easy for him to assign labels to the cells as you did in your example. The only reason why label assignments would be meaningless to the guards would be in the case where the number of cells were unknown.

So by simply beginning his explanation to the guards by saying, there are n cells let the this one over here be labeled cell #1 and all subsequent cells up to cell n labeled sequentially, here is my solution.

Title: Re: A Prisoner & 100 light bulbs
Post by Leonid Broukhis on Jul 16^th, 2004, 7:20pm

mattian,

If the prisoner never passes a cell without looking into it then he can infer all edges in the connectivity graph except ones that have, roughly, positive scalar product with the vector from X to the X-controlling cell). Then the prisoner will have to repeat the process starting from the X-controlling cell,
skipping known cells.

My question about cell labeling was because I thought that after the prisoner claims that he has the solution he could be brought (teleported) into an interrogation room and therefore he could lose the reference point.

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 16^th, 2004, 7:30pm

Leonid,

While I'm sure you're correct, I admit I don't fully understand your statement. Are you saying:
::

... that a prisoner starting at arbitrary cell x (which controls the bulb in cell y) can visit each cell sequentially to find cell y after pushing the button in cell x, and then move onto cell (x+1) and repeat the process?

::

Addendum:

Sorry Leonid, I missed your point about losing the reference point. You are correct, in my original problem statement I did not specify how he might explain the solution to the prison guards without being able to directly reference an arbitrary door by pointing at it, for example. Perhaps a clean way of handling this is to make the prisoner send the signal to the guards that he knows the solution by switching all the lights off, and then switching them all on sequentially (such that the lights are sequential not the button pushin) until they're all on. But unfortunately this would allow the prisoner to guess the solution - which is not allowed. I will clarify this issue somehow in the problem statement.

Title: Re: A Prisoner & 100 light bulbs
Post by Leonid Broukhis on Jul 16^th, 2004, 7:43pm

No need to hide anymore, I think.
No, it's the other way around. The main point is to press a different button at every pass. Consider a (potentially infinite) line of cells. Assume cell 0 does not control itself. Then the prisoner starts diverging sweeping movements looking at every cell every time and only pressing the button in rooms he has not visited before. This way he can infer all edges (a, b) where abs(a) > abs(b) and half of abs(a) == abs(b) depending on which way he went first.

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 16^th, 2004, 9:07pm

Indeed - the solution is quite trivial if you know the number of cells, as was that for the original "100 prisoners and the single light bulb in the switch room" puzzle. The optimal solution, however, is not as simple.

I will write your solution into my simulation and post the results - or you can :-).

Title: Re: A Prisoner & 100 light bulbs
Post by rmsgrey on Jul 17^th, 2004, 8:30am

on 07/16/04 at 12:00:33, mattian wrote:

Responses to your initial comments.
[...]
2. Could you rephrase this statement making careful distinctions between toggling the button vs. toggling the bulb.

The only information potentially gained by toggling the bulb in a previously unvisited cell is that the switch which controls it doesn't control the light in any previously visited cell.

Quote:

3. Agreed - although it should be noted that to switch any bulb on and observe it will require between 1 and 2 visits. I believe - using the most straight forward approach, given that the bulbs were all initially off - it would take closer to but not quite O(2n log n).

I got (without dynamic optimisations like observing a toggled bulb during a switching pass) 1.5n [lciel]log₂ n[rciel] - each stage consists of 2 passes, the first visiting n/2 cells and toggling their switches, and the second visiting all cells to determine the new state. It then requires [lciel]log₂ n[rciel] stages to identify each switch with certainty. Of course, there are some trivial optimisations - for instance you will always know the state of the bulb in the cell with the last switch and the bulb in the last cell visited in the second pass of each stage before you go in. And, of course, it's possible to adjust your strategy on the fly to account for cells that control their own light, and cells that are controlled by a switch toggled earlier in the current first pass of a stage.

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 18^th, 2004, 10:40am

Quote:

The only information potentially gained by toggling the bulb in a previously unvisited cell is that the switch which controls it doesn't control the light in any previously visited cell.

I assume you mean that this determination can be made if previously visited cells are revisited. The reason I had trouble accepting your statement is best illustrated in an example:

Five cells - {A, B, C, D, E}

If you've visited A, B and C and you toggle the switch in C (which happens to control E), no such determination (as your statement suggests) can be made without first revisiting A, B and C. Is that right?

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 18^th, 2004, 10:57am

Here are some of my thoughts about this problem:

One of the things I liked about it was that to truly optimise the solution, one is forced to employ different techniques for the different stages of the problem. There is no one-concept-fixes-all solution.

For instance, as RMS mentioned in the beginning, establishing the size of the prison is one of the important steps. this process can be optimised independently - or in fact, as part of one of the other processes.

While Leonid's solution to this portion of the problem will work it should probably be done at the same time that some reverse engineering on the wiring is done. Although I think an accurate knowledge of the size of the prison is less important in the beginning than it is later on.

There is a solution which uses no visits for this phase of the puzzle, but the result is resolved over time rather than being absolute in the beginning.

I have a simulation for this problem running at the moment and I will post results to this thread soon. I will also include results from the most basic strategies mentioned and those suggested as potential optimisations.

Title: Re: A Prisoner & 100 light bulbs
Post by rmsgrey on Jul 19^th, 2004, 4:14am

on 07/18/04 at 10:40:31, mattian wrote:

I mean that the only deduction you can possibly make, whatever future actions you take, is that the switch controls a light in some unspecified room you hadn't previously visited - in your example, by subsequently visiting all the cells, you can conclude that the switch in C controls the bulb in either D or E, but not which...

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 19^th, 2004, 5:34am

Okay - I see what you mean. You're saying that at any time, you are free to determine (through whatever means) that a switch either controls a light in a room that you've visited, or it doesn't. If it does, then you know which room it controls - if it doesn't, then you don't know which of the unvisited rooms it controls. Agreed.

Title: Re: A Prisoner & 100 light bulbs
Post by Nigel_Parsons on Jul 19^th, 2004, 11:11am

Looking for a ‘simple’ solution, within the bounds of the question.

We require:
Question 1 - What strategy can the prisoner employ to guarantee his freedom?

Question 2 - How can the prisoner minimize the number of cell visits he needs to make before he can declare the solution?

We know:
8. Despite any efforts he might make, the prisoner can not extract any positional state information from the button - it always looks the same.
9. All operations on the button must be performed from within the respective cell with the door closed.
10. No information from the outside world will be available to the prisoner when he is inside a cell - the only information available to him from within the cell, is the state of the light bulb in that cell, and what he decides to do with the button (if anything).

[Hide]It would seem the first action is to do a full round of the corridor, opening all cell doors to see if the cells are illuminated. Clearly this would be visible from the corridor, as the only time a door needs to be closed is to perform an operation on a button.
Whilst doing the rounds, note the sequence of on/off bulbs. Hopefully this will identify a unique sequence of rooms at some point in the tour. (this is the problem which may make the solution longer)

If a unique sequence has been identified, a mental map of all rooms can be made. Starting at an identifiable point (clockwise end of unique sequence?) do one more round trip. When you return to the known point you will know the total number of rooms. (second problem, all the rooms may form 2 or more identical sequences of rooms so you still do not know for certain that you know the number of rooms!)
At this stage you have not ‘visited’ a single room, thus helping with Q2.

Enter one room & toggle the switch.

Leave the room (leaving the door open) and do another tour of the corridor comparing the illuminations with your mental map. (at this stage you can confirm the total number of rooms as in repeated sequences only one difference in illumination will show)

You now know the number of rooms and the correlation between one switch and one bulb.
Now enter each room in turn, toggling its switch and then doing a full tour of the corridor. [/Hide]

For N rooms you will need to enter N-1 to get the full picture (the last switch/bulb can be identified by elimination), [Hide]but you may be tired from the repeated tours of the corridor.

Even if you are transported out to make your report you can identify the sequence by switching the last switch. This will restore the ‘unique’ sequence you found earlier, only each light will have been toggled once.

The only problem which will increase the number of visits required is if no ‘unique’ pattern appears on your first tour. You will then need to toggle sufficient switches to present a unique pattern. I leave that part of the problem to the next man (for now)[/Hide]

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 19^th, 2004, 11:44am

Hey Nigel,

If you've proved anything it is that despite all efforts on the part of a riddle author (or in my case, part plagiariser), loopholes will be found which will undermine the fundamental principles originally scoped for the riddle's solution. However, since your solution did not mention the phrases, "kill the guards, steal the key," I will forgive you your outside-the-box-yet-within-question-limitations solution and provide you with a sincere response. :-) Frankly I welcome the interest and have no desire to alienate the few people who show interest.

First of all, you did seem to miss the all encompassing disclaimer:

Quote:

12. If you think you have an answer which solves the problem using some trivial "kill the guards, steal the key" solution which doesn't contradict any of the limitations of this puzzle, then this statement says you're wrong.

This basically means you're not allowed to be creative and find gaps in the wording through which you can squeeze a solution. But again, it could be argued that your solution is not a "kill the guards, steal the key" solution and so I will be forced to add another disclaimer to the puzzle which states:

"13. If your name is Nigel_Parsons, your solution is wrong."

But, moving on...

While writing the riddle, I had the intention of including the disclaimer that doors close automatically, and faster than the prisoner can move from one cell to another. There are no gaps around the door through which light can pass. From the corridor, the prisoner can see the state of only one bulb at a time - when he is entering or leaving a room. Observing the state of a bulb counts as a visit.

I will add this to the problem statement.

But, moving on still...

::
Your mental map of the sequence is a good solution which ties in with my own. This does eliminate the need to visit cells simply to count them. However, the problem you mentioned regarding aliasing (or partial sequences interfering with the prisoner's ability to accurately discern the complete sequence) can be solved quite easily before any rooms are visited at all.
::

Given my obviously poor original phrasing of the puzzle, your solution makes sense. However, I, being the God of this riddle, have now modified the constraints and applied - most importantly - disclaimer #13.

Thanks :-)

Title: Re: A Prisoner & 100 light bulbs
Post by Leonid Broukhis on Jul 19^th, 2004, 3:48pm

I believe that the Nigel's solution is limited to cases where the initial state of the bulbs is unique wrt rotations. But even then, without doing a sweeping movement you can never be sure if a room you've going into is a completely new one that happens to match your expectation of what would be a result of your pressing a button somewhere else, or a room that you've seen already and that has indeed changed its illumination state.

[e] A typo.

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 19^th, 2004, 4:59pm

I agree with Leonid, however, the principle that Nigel used does form part of a solution which can establish the number of cells in an average of 10 visits. However, his solution alone is not sufficient to do this.

Title: Re: A Prisoner & 100 light bulbs
Post by Leonid Broukhis on Jul 19^th, 2004, 6:00pm

on 07/19/04 at 16:59:55, mattian wrote:

In an average of 10 visits to every cell, you mean? Is it for the potentially unbounded number of rooms, or for a number that is of the same order of binary magnitude as 1000?

As an improvement of my algorithm to find the number of rooms, I can suggest the sweeping movements of exponentially increasing depth (toggle 1 room to the left; 2 to the right; 4 to the left after skipping 1; 8 to the right after skipping 2, etc..., and a binary search afterwards. Requires visiting more rooms, but much less walking.

I'm contemplating a binary search of another kind: after establishing the number of rooms, do a round toggling every other room; observe results; then toggling every two rooms out of 4, etc. The the set of numbers of passes when the light in a room changed state gives you the number of the controlling room. I do not see ~~who~~ how to combine this pass with the pass to find out the number of rooms, though.

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 19^th, 2004, 6:40pm

Quote:

In an average of 10 visits to every cell, you mean?

Actually, no. I mean 10 visits total. - for a prison of about 100 cells. Although 1000 cells wouldn't much increase the number visits used to count the cells.

You make another good point about unbounded numbers of cells which is why I modified the riddle to keep numbers within managable maxima. My solution would suffer from practical limitations for exceedingly large numbers of total prison cells.

My solution has two parts - the first establishes the number of cells as an extremely accurate approximation. The second phase is the reverse engineering process which doubles as verification for the initial cell count.

In the example of 100 cells, 10 visits on average is enough to determine the number of cells in the prison - it could be done in fewer with higher risk of error, but 10 is a relatively small number in contrast to the complete solution.

Your method of switching every second, and then every third and forth, and so on is very close to my first solution - and in fact my current solution is built on that premise.

I would be very interested to see some simulation results for examples involving 100 cells. I'm holding out with my numbers because I myself am not yet satisfied with my own results - I promise to post the benchmark by the end of the week.

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 19^th, 2004, 7:03pm

A few more notes:

I have not yet had time to attempt the various strategies I've considered for this problem. My current solution seems fairly good although I have to rely on my own logical interpretation of why it should be a good solution. Only the numbers can tell us if it is or not.

Secondly, I should mention that I made a big mistake by creating a puzzle that would attract geniuses like RMS and Leonid - I have to omit Nigel for disclaimer abuse. The problem is that the responses I'm getting here are far too difficult for me to understand so I end up blabbering responses to you while trying to sound like I know what I'm talking about - so bear with me.

Also, although my method for counting the rooms is fairly cheap, it constitutes such a small percentage of the complete solution that it hardly seems worth it. However, if you don't manage to count the cells cheaply, I suppose it would have a higher percentage contribution, so I suppose it is justified after all.

Finally, I'm not keeping my solution to myself to be an annoying secret bearer - like a giddly little school-girl's, "I got a secret, nyah, nyah, nyah," mentality - I just don't want to corrupt your thought processes.

Title: Re: A Prisoner & 100 light bulbs
Post by Leonid Broukhis on Jul 19^th, 2004, 7:21pm

on 07/19/04 at 18:40:28, mattian wrote:

Actually, no. I mean 10 visits total. - for a prison of about 100 cells. Although 1000 cells wouldn't much increase the number visits used to count the cells.

Does the prisoner need to know the approximate number of cells (within
+/- constant or within an order of magnitude?), or the guaranteed upper bound? Would your algorithm work if there are, say, 103 cells, but the prisoner is told that there are around 100?

Quote:

In the example of 100 cells, 10 visits on average is enough to determine the number of cells in the prison - it could be done in fewer with higher risk of error, but 10 is a relatively small number in contrast to the complete solution.

Either I have a mental block switching from the unbounded number of cells to a limited number, or there is something wrong with that algorithm. Suppose there are exactly 100 cells. How many visits do you need to prove that there are exactly 100 cells?

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 19^th, 2004, 8:05pm

Quote:

Does the prisoner need to know the approximate number of cells (within +/- constant or within an order of magnitude?), or the guaranteed upper bound? Would your algorithm work if there are, say, 103 cells, but the prisoner is told that there are around 100?

The prisoner would have to know the approximate number of cells before resolving to a definite number - but he wouldn't have to be told - he could establish it on his own.

Quote:

The limited number of cells is definitely significant and different from the unbounded case - for practical reasons. I established a context for this riddle which allows solvers of it to use manageable numbers.

Had I posed the original puzzle as the original prisoner-lightbulb problem was posed, by saying there are exactly 100 cells then I doubt the significance of the number would be questioned. However, I left it open to the general case but included a limitation which kept the number within the grasp of a practical solution.

There are properties of the prison which become hazy as the number of cells becomes too large.

Quote:

How many visits do you need to prove that there are exactly 100 cells?

Unfortunately this question can not be answered with a number. It depends on the distribution of light bulb status. The more 'ambiguous' the distribution, the more visits will be necessary - but this can be determined on the fly. After visiting an average of 10 cells, the prisoner will know the exact number of cells - guaranteed. But the number 10 is not guaranteed - it's a guaranteed average, for accurate results.

It's difficult not to be cryptic - sorry about that.

Title: Re: A Prisoner & 100 light bulbs
Post by Leonid Broukhis on Jul 19^th, 2004, 11:53pm

on 07/19/04 at 20:05:57, mattian wrote:

But the answer to my question does have a numerical answer. It is the number of visits that is sufficient to determine the number of rooms under the worst conditions.

Quote:

After visiting an average of 10 cells, the prisoner will know the exact number of cells - guaranteed. But the number 10 is not guaranteed - it's a guaranteed average, for accurate results.

If 10 is the average, the what is the minimum and what are the conditions to achieve it? My feeling is that there is a flaw somewhere. We can play a game: I'll generate a graph with 90+random(20) nodes and randomly assign the starting values of bulbs. Then, without loss of generality, I'll pick a node ant tell you whether it is light or dark there (this vill be visit #1). Then you tell me what to do. Are you game?

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 20^th, 2004, 5:32am

Quote:

But the answer to my question does have a numerical answer. It is the number of visits that is sufficient to determine the number of rooms under the worst conditions.

It would, I suppose, be theoretically possible for it to take as many as 203 visits for 100 cells in the worst case. But this is an extremely unlikely outcome.

Quote:

Are you game?

It's a great idea, but it won't work. I would have to ask you questions about things that I see - this is not simply a logic puzzle with 1's and 0's. Preliminary mathematics is part of it, and throwing 1's and 0's back at each other is not sufficient for me to arrive at a solution.

I could ask you for the additional information I would have if I were the prisoner, but I will leave it to you to decide if you want to be asked. I don't want to give you my solution too early - IT'S ALL I'VE GOT!!! :-)

However, we can simulate it given the 90 (+-20 nodes) but there is a problem here too. That leaves me with a range of 70 through 110 which is far less accurate than the number with which I would start out as the prisoner. With the numbers you've given me, I would need an average of about (and I'm just guessing here) 30 to 40 visits to resolve an accurate number.

Having said all that - I'm a good sport and am always willing to try simulations like that.

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 20^th, 2004, 5:51am

Perhaps I should add some more notes here:

Much like a new software development initiative, the first run of a new riddle is likely to be flawed due to all the things that were missed in the unit testing. I think this riddle is holding up fairly well, however, I would make one change if I did it again; I would modify the riddle to be entirely specific rather than an appeal for the general solution for n cells.

Many riddles have annoying tricks in them. For example:

In my hand I have two American coins which add up to 30 cents - one of them is not a quarter. What coins am I holding?

On a slimey-trick scale from 1 to 10, with 1 being fairly innocent and ten being really slimey, this riddle is about a 7.

Solution:
::
One of them is not a quarter, but the other one is.
::

There is another riddle which is part of this forum (in the medium section, I think).

There are two rooms - in one room there are three switches, in the other room there are three light bulbs. All the usual restrictions apply. With one visit to the room with the light bulbs, determine which switch controls which light bulb. The light bulbs are initially off.

Solution:
::
Switch two on, wait a while, switch one off. Enter the room with the bulbs, and discretely identify the bulbs which are respectively on, off and hot.
::

On the slimey-trick scale, this riddle scores about a 3, because the solution is entirely valid but there is some dependency on practical properties of the problem.

My solution to counting the cells in this lone-prisoner riddle scores about a 1. The solution is valid for manageable sizes of the prison. This is because - and this is a hint, so be careful if you don't want it -

::
The shape of the prison is relevant in the solution
::

Purely theoretically, the size of the prison is not relevant to the solution, but in practice, the size does impose practical limitations on the solution's method.

The same limitations apply to the 3-bulb riddle:
::
In theory, with a highly accurate thermometer, it could be argued that the 3-bulb problem would be solveable up to, say, 60 switches and 60 bulbs. Turn on all the bulbs and then turn them off one by one every second. After a minute and the switches are all off (but one, of course) enter the bulb room with your thermometer and start measuring. This solution works in theory but in practice it would be very difficult to master.
::

Title: Re: A Prisoner & 100 light bulbs
Post by Leonid Broukhis on Jul 20^th, 2004, 8:11am

One more disclaimer to the puzzle is needed:
- It is guaranteed that the situation where every cell controls itself will not happen.

And I was thinking of asking that question: while in the corridor, how many doors can the prisoner see at once? In my purely theoretical mental model it is 1, so the prisoner needs up to 5 visits just to check whether the prison has 2 cells or more:
1. go to room A, press the button. If the light changes, then we're done, otherwise
2. go to the left (room B), press the button. If the light changes, we're done, otherwise
3. go to room A. If the light is the same as when we left it (room B controls some other room), we're done, otherwise press the button and
4. go right (room C) If the light is the same as in room B when we left it, we're done (C is definitely not the same as B) otherwise press the button and
5. go to room A. If the light is the same as when we left it, we're done (C controls some other room), otherwise it is proven that both B and C control A, and therefore B == C.

By the way, isn't using the shape of the corridor in a way akin to having a (natural, if you like) measuring device? I can count the width of the corridor, the length of a chord and the distance between rooms in feet, and estimate the circumference of the corridor and the number of rooms with reasonable precision, but this is cheating. As you said "no measuring devices are allowed",
you pretty much implied that you want to create a purely logic puzzle with 1's and 0's.

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 20^th, 2004, 8:36am

Quote:

It is guaranteed that the situation where every cell controls itself will not happen.

I don't see that this is a necessary disclaimer - it seems to me as though it would merely be a convenience should such a situation occur. Am I missing something?

Quote:

...this is cheating

Using a measuring device in a riddle is hardly elegant. And while pure logic is perfectly elegant, mathematics is elegant too. The key here is not the use of a measuring device or the prisoner's ability to accurately calculate the circumference of the prison. The key is to arrive at a reasonable approximation which can be resolved over time (or visits). In other words, with an extremely accurate measuring device and an atomically perfect circular prison, the number of visits to cells in order to count them would be zero.

I don't discount estimation as part of a logical solution. It provides a range within which you can work, so to answer your question specifically - there is no need for the prisoner to arrive at an accurate measurement, but basic measurement at a glance with some paces here and there can go along way towards eliminating cells that are quite blatantly neither the first nor the last cell. All the prisoner needs to know is that he has circled the prison once and found a point which matches a known sequence.

Quote:

you pretty much implied that you want to create a purely logic puzzle with 1's and 0's.

And I tried very hard not to do that. And I don't believe that a solution which uses an initial scan and some rough estimations is out of bounds in the logical realm. I did mention in the original list of disclaimers (and I acknowledge now that it would have been better placed in the list of facts) that from within the corridor, the prisoner can see only the corridor disappearing around the corner with the doors to the cells on the outer wall.

Please don't feel cheated - this is only the first part of this puzzle.

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 20^th, 2004, 8:54am

Also, the circular prison was specifically and carefully chosen for this riddle for two reasons. Firstly because it simulates an infinitely invariant corridor of doors AND at the same time, provides the means to establish the number of cells. The problem and the solution are wrapped up in the same package - in this case, a circular prison.

Had I opted for purely 1's and 0's logic, I might have chosen a shape like a straight line which is curved in 4 dimensional space-time such that it's one end is connected to it's other end seamlessly, while appearing perfectly straight and infinite in 3 dimensional space. But then we might have argued that for small values of n, the prisoner would see himself n cells down the corridor. Actually - that sounds like the recipe for an interesting puzzle.

When RMS mentioned the measuring device, I dismissed it because I pictured a prisoner on his hands and knees with a ruler blatantly defeating the purpose with measurements accurate to the last inch. The naked prisoner, however has only a few tools at his disposal, common sense and logic. Plus - and I forgot to mention this earlier - he's infinitely intelligent - which means he knows how to use his rough observations to come up with a reasonable estimates; and, ultimately, resolve them through parity-type verification.

Title: Re: A Prisoner & 100 light bulbs
Post by rmsgrey on Jul 20^th, 2004, 9:27am

on 07/20/04 at 08:11:53, Leonid Broukhis wrote:

One more disclaimer to the puzzle is needed:
- It is guaranteed that the situation where every cell controls itself will not happen.

With a 3 cell prison (because I'm lazy) where each cell controls itself:

Start.
Visit cell 1(A). Leave the light off when you go.
Visit cell 2(B). Leave the light off when you go.
Visit cell 3(C). Leave the light off when you go.
Visit each cell in turn up to, say, cell 42(C), toggling the switch twice to establish that the cell controls itself and leave the light off.
Visit cell 43(A). Turn the light on.
Visit cell 42(C).
Visit cell 41(B).
Visit cell 40(A). Find the light on and declare you know the situation completely - a 3 cell prison where each cell controls itself.

Why the need for an additional disclaimer to eliminate this situation? If you turn around too soon, then when you hit cell 0 and start into negative numbers, you just keep turning lights off in the negative numbers until you get bored and turn around again, leaving the last cell you visited lit up... repeat until you loop back on yourself or find a cell that doesn't control itself

Title: Re: A Prisoner & 100 light bulbs
Post by Leonid Broukhis on Jul 20^th, 2004, 9:53am

on 07/20/04 at 08:36:13, mattian wrote:

I don't see that this is a necessary disclaimer - it seems to me as though it would merely be a convenience should such a situation occur. Am I missing something?

In this case all rooms are identical, and you cannot refine your original estimate of the number of rooms.

Quote:

The key is to arrive at a reasonable approximation which can be resolved over time (or visits).

Isn't 100 rooms from the problem statement a reasonable approximation already?

Quote:

In other words, with an extremely accurate measuring device and an atomically perfect circular prison, the number of visits to cells in order to count them would be zero.

Naturally.

Quote:

I don't discount estimation as part of a logical solution. It provides a range within which you can work, so to answer your question specifically - there is no need for the prisoner to arrive at an accurate measurement, but basic measurement at a glance with some paces here and there can go along way towards eliminating cells that are quite blatantly neither the first nor the last cell.

From where I stand, some paces here and there do measure something, and therefore are a measuring device. Even if the prisoner walks along a chord then tries to estimate the angle between the chord he'd just walked and the next one, he is using a (mental) protractor.

Quote:

All the prisoner needs to know is that he has circled the prison once and found a point which matches a known sequence.

I see. Indeed, if the prisoner assumes that his estimation is no more than one off, some sequences will allow him to persist in his delusion, e.g. when in fact it is two or three off.

Quote:

I did mention in the original list of disclaimers (and I acknowledge now that it would have been better placed in the list of facts) that from within the corridor, the prisoner can see only the corridor disappearing around the corner with the doors to the cells on the outer wall.

With how many doors? Zero doors is an acceptable number of doors. This disclaimer means that there are no other distinguishable features except doors in the corridor, that is all.

Quote:

Please don't feel cheated - this is only the first part of this puzzle.

Well, I've solved the puzzle to my satisfaction. After finding the number of cells, I'll need no more that 1.5*N*log2(N) visits (optimizations are possible because I can observe the partial results during the switch manipulation pass, and, if I'm lucky, deduce something from it immediately or something that will allow me to skip some visits later; and, obviously, the rooms that happen to control themselves do not need to be visited after that is discovered). And to find the exact number of rooms takes no more than 2*N+1 visits using the purely logical game.

Title: Re: A Prisoner & 100 light bulbs
Post by Leonid Broukhis on Jul 20^th, 2004, 10:06am

rmsgrey,

you're right, and, actually, my algorithm to find the number of rooms covers that case with the same 2*N+1 maximum and no need for boredom. What we need is to find "two" rooms that control the starting room, then add the distances. This algorithm works even when one distance is zero. How could I be so blind?

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 20^th, 2004, 1:21pm

Trying very hard to get away from the ground flack here - I fear I'm being shot down anyway. But here goes,

Quote:

Visit cell 1(A). Leave the light off when you go.
Visit cell 2(B). Leave the light off when you go.
Visit cell 3(C). Leave the light off when you go.
Visit each cell in turn up to, say, cell 42(C), toggling the switch twice to establish that the cell controls itself and leave the light off.
Visit cell 43(A). Turn the light on.
Visit cell 42(C).
Visit cell 41(B).
Visit cell 40(A)

Quote:

In this case all rooms are identical, and you cannot refine your original estimate of the number of rooms.

If you know the approximate number of cells is three - then you won't get to visit 43. Once you are sure you have passed your starting point you simply need to make a change that you can detect in the next round - hence my worst case scenario of 203 visits in a 100 cell prison.

Quote:

Isn't 100 rooms from the problem statement a reasonable approximation already?

No because the prisoner doesn't know that. As solvers of the puzzle, we know more than the prisoner - we have to set up the paramters within which we can test the theory. We set up a test case of 100 cells, and then solve the problem as if we didn't know the number of cells.

Quote:

Point taken. But where do you draw the line. If I use only my eyes, and I size something up, would you call my eyes a type of measuring device? My solution doesn't need paces - It can be done by observation - except in very extreme cases - which can be handled differently on the fly.

Quote:

..if the prisoner assumes that his estimation is no more than one off, some sequences will allow him to persist in his delusion, e.g. when in fact it is two or three off.

Well if he assumes that he is only one off, then yes, I'm sure he would arrive at a risky result - but who says he makes that assumption?

Quote:

With how many doors? Zero doors is an acceptable number of doors. This disclaimer means that there are no other distinguishable features except doors in the corridor, that is all.

As many doors as he can see. It depends how wide the corridor is, how large the prison is and how many cells there are in the prison. And discerning doors as the only distinguishable features is all he would need.

Quote:

Well, I've solved the puzzle to my satisfaction.

I suppose before you leave - since I gather you've lost interest in the puzzle - I should post my solution to the cell count.

By standing infront of one of the doors, facing back towards the corridor, the prisoner looks to his left or his right. He counts the number of doors he can see in the chosen direction. He then gauges the distance to the inside wall of the corridor compared with that to the door immediately on his right or left. He can pace it out roughly if it isn't clear - but accuracy here is not too important. All he's looking for here is a means to roughly express the width of the corridor as some proportion of the distance between doors, which he will use as his units in the following calculation.

Suppose, for example, that the width of the corridor is x - for which the unit of measurement is doors - and that he saw d doors to his right. Then the approximate number of cells in the prison is described in the equation:

sin a/4 = 1 - x/d(2[pi] - a/2) ... (1)
and
a = 2[pi](1 - 2d/n) ... (2)

where

n is the number of cells in the prison
x is the width of the corridor (given in distance-between-door units)
d is the number of visible doors to the left or right

Leonid, you remember the mathematics question I posed in the other forum which tried to solve for a in equation (1). Well this was why I needed it. My simulation solves for a, by running through a sequence of values for a until the equation is satisfied. a by the way is the angle in radians between radii of the prison which intersect with the two furthest visible doors to the left and right - as observed by the prisoner. Resolving values for n that satisfy the equations above, yields a surprisingly accurate estimate of the number of cells in the prison.

I don't see this portion of the solution as measurement solution as much as mathematical one.

The prisoner, with his new estimate, then picks a door and enters it making note of the state of the bulb in that room. He moves onto the next door and does the same thing. He is looking for a short sequence which is discernable within the resolution of error he is expecting from his estimate. In other words, if the error in his estimate is (+-3 cells) then he's looking for about a 7 cell sequence that is unique with respect to a rotation of 3 cells. He then runs once around the corridor counting the doors until he reaches his estimate and begins to open the doors as he did before. Either they match his original bit map or they don't If they don't the necessary adjustment will be clear by the offset evident in the rotation-protected sequence.

As it turns out - the error in the inital estimate is easily kept within one or two cells - which requires only 5 visits before the lap of the prison and then 5 at the end. If no unique sequence is found in 5 initial visits, then visits need to be added to the first 5 - but not the second.

THE END (of part 1)

If you feel that my solution is not valid - let me know.

Title: Re: A Prisoner & 100 light bulbs
Post by Leonid Broukhis on Jul 20^th, 2004, 2:46pm

mattian,

your solution would be valid if n is a function of x and d (and we're not sure), and even if it is, if the prisoner has a way to estimate the upper bound of the error in his estimation of n. E.g. the sequence 00100 is good enough for errors up to +/-2 but fails miserably if the actual error is +/-3. And nothing prevents the prisoner from creating a unique sequence during his first 5 visits; that is, within your solution, there is no need for more that 10 visits to find the number of rooms.

And if we're into definition nitpicking, the only non-self-referential clause of Webster's def. of "measure, v." is "to estimate or appraise by a criterion" (as in "to estimate or appraise the width of the corridor by the distance between rooms"); so there.

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 20^th, 2004, 3:29pm

The error is not a mystery to the prisoner - It depends on the size of the units he chooses for his appraisals. For example, if he chooses to establish dimension in 2 meter increments, ignoring any fractions thereof, the error in his measurement is known. All he has to be sure of, is that within the constraints of the units he's chosen, his dimensions are accurate.

Quote:

your solution would be valid if n is a function of x and d (and we're not sure)

Why is there any question as to whether n is a function of x and d? Is it because n cannot be expressed as the subject of the equation? I might accept that, by strict definition, n is not a function of x and d - but values that satisfy the equation, consistently produce a result which is the correct result - which means whether or not it is a function, is meaningless.

My only concern with the equation was that I wanted it to look a bit prettier.

But here's a question: I'm a first time puzzle author who put some time (and it clearly wasn't enough) into creating a puzzle that others might find interesting. Quite honestly, I'll let you keep your true opinions to yourself, but I'm intrigued by the sudden hostility towards me and my solution since it incorporated verification of an intial approximation.

For example: Suppose the prisoner used your initial solution - ie. pick a room, check a door to the right, come back, flip the switch, check the room again, look for a difference, repeat with the next room until a difference is found, then start again going the other way, add the counted cells from each direction together.

Okay, now suppose, you went to the right first and found that the zeroth switch controlled the +2nd room. And suppose by standing in the zeroth position, you could see the -5th room. It wouldn't be necessary for you to test rooms -1, -2, -3, -4 or -5. In fact, in this situation you move three doors in the negative direction and then you wouldn't have to test -6, -7 or -8 either. Why can you eliminate these cells? Because it is evident that the circle is larger than to allow the +2nd room to be the same room as the -8th room (because you can see them at the same time).

The solution I've mentioned makes a similar optimisation. It simply eliminates a collection of rooms based on the size of the circle.

Since I will be called a measurer regardless of my wording, I may as well take advantage of it and say that if the prisoner did measure the width of the cell using the devices he calls feet, and similarly the period of the repeating doors, his calculation will produce a result within 1% accuracy for 100 doors.

Finally - I didn't join this forum to fight with people :-). I joined this forum because since leaving my home town - four years ago - where I had friends with whom I could exchange this sort of puzzle, I have been hard pressed to find more people who share this interest. This forum is what I have found so far - SO BE NICE! >:(

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 20^th, 2004, 3:37pm

Quote:

nothing prevents the prisoner from creating a unique sequence during his first 5 visits

Not true. The sequence 00000 has no edges and is useless. Conversely the sequence 00111 is extremely useful. 00100 is somewhere in the middle. 01010 requires too much resolution (accuracy in the estimate) to be useful.

That is why - and this is only my current theory on this (which is why I was curious about other people's solutions) - the prisoner must continue until he finds a sequence with a bit that repeats e times with at least one edge, where e is the known upper bound of the error. Or at least until there are e distinctly recognisable edges in the sequence.

Title: Re: A Prisoner & 100 light bulbs
Post by Leonid Broukhis on Jul 20^th, 2004, 3:47pm

mattian,

Please do not take it so hard. I am usually nice. But why not split this puzzle into two? E.g.

You are standing (naked with empty hands) in a circular corridor with evenly spaced identical locked doors in the outside wall. While standing with your back to a door, you can see a few doors to your left and to your right. There are no other distinguishing features in the corridor. Estimate the number of doors.

This is a perfect math puzzle in and of itself. Mixing the two (a geometry/calculus puzzle and an operational puzzle) is, IMO, akin to allowing the prisoners in that other puzzle to play with the switch to leave the light in intermediate states and to make decisions based on the brightness of the light using the knowledge of the physical properties of the switch and the light bulb. But, of course, you can reject this analogy if you don't like it.

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 20^th, 2004, 3:50pm

Quote:

You are standing (naked with empty hands)

Now it's just getting sordid.

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 20^th, 2004, 4:02pm

I'm not taking it hard at all - I'm fairly thick skinned but annoy myself if I irritate people.

No - regarding your suggestion of splitting the puzzle up - I do take your point. However, one of the things I find interesting about puzzles is when they force us to think about the problem. I agree that based on my initial phrasing of the problem, my solution is not very different from Nigel's solution in that it seems to take advantage of those restrictions not specified in the problem statement. I realised a few days ago that I should have mentioned that the corridor was well lit and that the length of the period between the repeating doors was equal to the width of the corridor. With this information no measurement would be needed save for counting the doors as I mentioned in my solution.

I don't think there is any issue in mixing strategies into one ultimate solution. The big problem with the education system at the moment, for example, is that students are tested within known reference frames - they recognise problems as those derived from particular chapters, and tank when a question requires the combination of skills from two chapters at the same time.

I did post half this problem as a purely geometry-related problem in the putnam forum entitled "Geometry Problem" and it deals with the cell counting part of the solution to this problem.

Having said all that - I think you make a valid point, but I think my mistake here - and I've learned from it - was that I tried to be too generic in the problem statement.

I do have another puzzle brewing - and I intend to get it right this time. Watch out for a topic called One-Dimensional-Maze.

Assuming, though, in this puzzle, that the number of cells in the prizon is known after 10 visits because the accuracy of the calculation yields a result within 1%. And that the number of cells is precisely 128. I'm still curious as to how low the number of visits can go and whether in fact 1.5*N*log2(N) is the absolute lowest. I believe my numbers are reflecting that at the moment.

P.S. I intend to be naked in the 1D-Maze.

Title: Re: A Prisoner & 100 light bulbs
Post by Leonid Broukhis on Jul 20^th, 2004, 4:48pm

on 07/20/04 at 16:02:56, mattian wrote:

I realised a few days ago that I should have mentioned that the corridor was well lit and that the length of the period between the repeating doors was equal to the width of the corridor. With this information no measurement would be needed save for counting the doors as I mentioned in my solution.

Perfect!

Quote:

Assuming, though, in this puzzle, that the number of cells in the prizon is known after 10 visits because the accuracy of the calculation yields a result within 1%. And that the number of cells is precisely 128. I'm still curious as to how low the number of visits can go and whether in fact 1.5*N*log2(N) is the absolute lowest. I believe my numbers are reflecting that at the moment.

It can be improved. In cases when during a "setting" pass a change of state is observed, there is no need to visit that cell again during the following "observation" pass. So 1.5*N*log(N) is sufficient, but the average is definitely lower.

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 20^th, 2004, 5:06pm

I am still optimising my solution for this part of the puzzle and still intend to post the exact results before the end of the week - unfortunately I also have a job which means I am limited in the amount of time I have available to play. We'll see how those values compare to 1.5 N log2(N).

P.S. Thanks for the input. Question: Should I modify the problem statement or leave as it is?

Title: Re: A Prisoner & 100 light bulbs
Post by Leonid Broukhis on Jul 20^th, 2004, 5:11pm

on 07/20/04 at 17:06:44, mattian wrote:

Question: Should I modify the problem statement or leave as it is?

How about:

Addendum 2:
1. The prisoner does not have access to any measuring equipment, and he does not need any, because the width of the corridor happens to be equal to the distance between doors + the door width.

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 20^th, 2004, 5:21pm

Noted. Added. Thanks.

Title: Re: A Prisoner & 100 light bulbs
Post by rmsgrey on Jul 21^st, 2004, 5:23am

on 07/20/04 at 13:21:12, mattian wrote:

[visit lots of cells in a 3 cell prison]

If you know the approximate number of cells is three - then you won't get to visit 43. Once you are sure you have passed your starting point you simply need to make a change that you can detect in the next round - hence my worst case scenario of 203 visits in a 100 cell prison.

I was assuming that you had no basis for an approximation of the number of cells other than observing lights. Even then, there are obvious improvements possible; I wanted to demostrate that it was possible to solve the scenario, by giving a simple solution, not a good one...

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 21^st, 2004, 5:55am

Understood - however, your example was supporting the motion for the addition of a constraint which guarantees that initial state of bulbs is not constant throughout (i.e. all 1's or all zeros). I would prefer not to add this constraint as I don't think it is necessary in order to solve the problem. It may of course push our averages up a bit; but that's fine because it is due to an inherent property of the problem.

Furthermore, if we are to rule out these two initial states, I believe we would have to rule out the initial state for a four cell prison of "1010", or for a six cell prison "000111".

If we were to impose the constraint it would have to say, "The frequency of the signal produced by visiting the cells must be exactly one wave pattern per revolution." - which I think is too restrictive.

Title: Re: A Prisoner & 100 light bulbs
Post by rmsgrey on Jul 21^st, 2004, 7:04am

No I wasn't - at least not intentionally. I was arguing against banning the situation where each room controlled itself. When I talked about leaving lights off, I was using it as shorthand for entering the cell, toggling the switch to verify that the cell controls itself, and then re-toggling if necessary to turn the light off. The point is that my method (inelegantly) discovers the number of cells in the situation where every cell controls itself (and you have no approximate number available) contrary to Leonid's earlier assertion

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 21^st, 2004, 7:16am

Oh - right - sorry. I got myself confused. The initial motion by Leonid to ban the situation where all cells controlled themselves morphed in my mind into a the situation in which all bulbs are initially zero. Little bit of a brain hiccough on my part.

Now that I have everything screwed back into place, I remember my original issue. I thought you were supporting Leonid's constraint by saying that if it were not there, the prisoner would do laps round the prison adinfinitum because he would never find an edge (or a distinction between one cell and another). But I've just reread your argument and realised that you were on my side during that brief period - although I think your choice of 42 as the number to start suspecting something is up is a bit high. If you're getting dizzy, I think it's safe to assume you've been around a few times :-).

Title: Re: A Prisoner & 100 light bulbs
Post by rmsgrey on Jul 21^st, 2004, 8:01am

I was assuming the guy had no sense of direction, so couldn't tell even approximately how many times he'd been round the circle...

Title: Re: A Prisoner & 100 light bulbs
Post by mattian on Jul 21^st, 2004, 8:08am

Well I suppose if the circumference of the corridor were 300 miles and each cell were 100 miles wide, then he wouldn't get very dizzy - just tired.

Title: Re: A Prisoner & 100 light bulbs
Post by Padzok on Sep 8^th, 2004, 4:37pm

Here is my effort. It's a genuine attempt, so if I have misunderstood the question, be gentle. I am not trying to be a smart alec. :-[

At the same time, I make no claims to being a mathematician, so feel free to rip the mistakes to pieces and I may try again depending on what I learn. ;D

I believe the guy has like total recall. If not, then do not bother reading the answer, just tell me I am wrong.

:: [hide]

He starts off in room 1. He hits the switch twice to see if it is the switch for the room he is in. Let's say it is not. This is one visit.

He goes 1 room clockwise, which we will call room 2. During this visit he toggles the switch to see if it affects the room. Let's say it does not. This counts as one visit.

He makes his second visit to room 1 and hits the switch. He goes back for his second visit to room 2, to see if there has been any change.

If room 2 is not changed, he goes back to room 1 to un-toggle ie to re-set whichever room had been changed.

He then does room 3 and he repeats this procedure for every room clockwise until he comes to room x which is controlled from room 1.

He then repeats the procedure anti-clockwise until he finds room x again in the anti-clockwise direction.

I assume none of the rooms he has found thus far control themselves, as this is the worst case scenario.

It follows then that he now has the following information.

He knows how many rooms there are N (by adding how many steps from room 1 to x clockwise, to how many anti-clockwise).

He also knows (remembers) the state of the lightbulb in every room.

He has so far made this many visits:

To room x, 4 times
To every other room apart from room 1, twice [so that is 2(N-2)]
To room 1 : for (N-2) rooms, twice each; for room x, 4 times

So Visits, V= 4 + 2(N-2) + 2(N-2) +4 = 4N

He now goes to room 2 (one more visit). He toggles the switch. He then has to visit each of the rooms one after the other until he finds the bulb which has been toggled by the switch in room 2.

Once found he goes back to room 3 and repeats the procedure.

I may be way off here, but I am looking for worst case scenario rather than average.

So for room 2, he may have to visit every room apart from x, before he finds the right one (call it y), so that is N-1.

For room 3, he may have to visit every room apart from x and y before he finds the right one, so that is N-2.

I'm not sure how to add that up, but I think that amounts to N(N-1) visits for this second stage.

So in total V = 4N + N(N-1) = 4N + N [sup2] - N = N [sup2] +3N = N (N+3)

So for room 2, he may have to visit every room apart from x, before he finds the right one (call it y), so that is N-2 (if he has not found it after N-2 rooms, he knows it is the one left).

For room 3, he may have to visit every room apart from x and y before he finds the right one, so that is N-3.

I'm not sure how to add that up, but I think that amounts to a sum from 1 to (N-2)

I think that is 0.5(N-2) (N-2+1) = 0.5 (N-2)(N-1)

So in total V = 4N + 0.5 (N-2)(N-1)

(The formula looks so ugly I am sure it is wrong.)

This is for worst case scenario.

For 100 rooms it amounts to

V= 400 + 0.5 x 98 x 99 = 5251

Any rooms which control themselves only have to be visited once and are 2 less visits to room 1 in the first stage.

Also I would imagine that the average number of visits for stage 2 would be half of what I have for the worst case.

[/hide] ::

So (a) does my suggestion work? and (b) how far from the ideal is it?

Title: Re: A Prisoner & 100 light bulbs
Post by rmsgrey on Sep 9^th, 2004, 5:07am

It looks like your method works, and will get a solution, but if you look at the rest of the thread, I've proposed a better solution for the second stage - O(nlogn) rather than your O(n² and Leonid Broukhis has a solution for the first stage with worst case time 2N+1 compared to your 4N. Mattian also has a solution for the first stage, which relies on using the physical properties of the prison to get a reasonable approximation of the number of cells, and then refining that approximation (which may not be as satisfactory a solution, depending on your taste)

On the other hand, both Leonid and I use similar methods to identify the layout to those you used, in each case with one modification - for the first stage, identifying the switch that controls the light in the first room rather than the light controlled by the switch in the first room, and for the second stage, identifying sets of lights controlled by sets of switches rather than each light-switch pair individually.

Title: Re: A Prisoner & 100 light bulbs
Post by Padzok on Sep 9^th, 2004, 2:53pm

Thanks for the feedback on my attempt.

I've taken your suggestion and re-read the earlier posts. Some of them sunk in a bit further second time round. :-/

I think I'll have to read over them again another day to see more fully what the full methods are.

With the method that gives N for certain in a maximum of (2N+1) visits, what does the prisoner know about the state of the lights in the rooms after those (2N+1) visits?

Title: Re: A Prisoner & 100 light bulbs
Post by rmsgrey on Sep 9^th, 2004, 3:30pm

For the 2N+1 visits, the prisoner first visits room 0. He then visits each room in turn, toggling the switch and returning to room 0 between rooms until he finds the nearest room in each direction that controls the light in room 0. By the terms of the puzzle, those two rooms are the same room, so you know N. At that point, you know the state of room 0 and of the room that controls the light in room 0, and any rooms that control their own lights. I guess if you want to know a complete initial state, you'd need up to another N-2 visits to check the state of the remaning bulbs, bringing you up to 3N-1 total. Of course, there's a special case where room 0 controls itself - in which case you toggle each switch that doesn't control itself twice on the way through, and know the complete initial state of the bulbs for free, as well as having a shorter average case (if a room doesn't control itself you don't need to check if it's room 0 when room 0 does)