Author |
Topic: A Prisoner & 100 light bulbs (Read 2540 times) |
|
mattian
Senior Riddler
 
Gender: 
Posts: 404
|
 |
Re: A Prisoner & 100 light bulbs
« Reply #25 on: Jul 20th, 2004, 5:32am » |
 Quote  Modify
|
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:
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.
|
| « Last Edit: Jul 20th, 2004, 6:07am by mattian » |
 IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: A Prisoner & 100 light bulbs
« Reply #26 on: Jul 20th, 2004, 5:51am » |
Quote Modify
|
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.
::
|
| « Last Edit: Jul 20th, 2004, 8:59am by mattian » |
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: A Prisoner & 100 light bulbs
« Reply #27 on: Jul 20th, 2004, 8:11am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: A Prisoner & 100 light bulbs
« Reply #28 on: Jul 20th, 2004, 8:36am » |
Quote Modify
|
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:
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.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: A Prisoner & 100 light bulbs
« Reply #29 on: Jul 20th, 2004, 8:54am » |
Quote Modify
|
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.
|
| « Last Edit: Jul 20th, 2004, 8:58am by mattian » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: A Prisoner & 100 light bulbs
« Reply #30 on: Jul 20th, 2004, 9:27am » |
Quote Modify
|
on Jul 20th, 2004, 8:11am, 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
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: A Prisoner & 100 light bulbs
« Reply #31 on: Jul 20th, 2004, 9:53am » |
Quote Modify
|
on Jul 20th, 2004, 8:36am, 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.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: A Prisoner & 100 light bulbs
« Reply #32 on: Jul 20th, 2004, 10:06am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: A Prisoner & 100 light bulbs
« Reply #33 on: Jul 20th, 2004, 1:21pm » |
Quote Modify
|
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:| 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. |
|
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.
|
| « Last Edit: Jul 20th, 2004, 5:16pm by mattian » |
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: A Prisoner & 100 light bulbs
« Reply #34 on: Jul 20th, 2004, 2:46pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: A Prisoner & 100 light bulbs
« Reply #35 on: Jul 20th, 2004, 3:29pm » |
Quote Modify
|
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! 
|
| « Last Edit: Jul 20th, 2004, 3:34pm by mattian » |
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: A Prisoner & 100 light bulbs
« Reply #36 on: Jul 20th, 2004, 3:37pm » |
Quote Modify
|
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.
|
| « Last Edit: Jul 20th, 2004, 3:43pm by mattian » |
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: A Prisoner & 100 light bulbs
« Reply #37 on: Jul 20th, 2004, 3:47pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: A Prisoner & 100 light bulbs
« Reply #38 on: Jul 20th, 2004, 3:50pm » |
Quote Modify
|
Quote:| You are standing (naked with empty hands) |
|
Now it's just getting sordid.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: A Prisoner & 100 light bulbs
« Reply #39 on: Jul 20th, 2004, 4:02pm » |
Quote Modify
|
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.
|
| « Last Edit: Jul 20th, 2004, 4:04pm by mattian » |
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: A Prisoner & 100 light bulbs
« Reply #40 on: Jul 20th, 2004, 4:48pm » |
Quote Modify
|
on Jul 20th, 2004, 4:02pm, 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.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: A Prisoner & 100 light bulbs
« Reply #41 on: Jul 20th, 2004, 5:06pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: A Prisoner & 100 light bulbs
« Reply #42 on: Jul 20th, 2004, 5:11pm » |
Quote Modify
|
on Jul 20th, 2004, 5:06pm, 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.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: A Prisoner & 100 light bulbs
« Reply #43 on: Jul 20th, 2004, 5:21pm » |
Quote Modify
|
Noted. Added. Thanks.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: A Prisoner & 100 light bulbs
« Reply #44 on: Jul 21st, 2004, 5:23am » |
Quote Modify
|
on Jul 20th, 2004, 1:21pm, 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...
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: A Prisoner & 100 light bulbs
« Reply #45 on: Jul 21st, 2004, 5:55am » |
Quote Modify
|
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.
|
| « Last Edit: Jul 21st, 2004, 6:00am by mattian » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: A Prisoner & 100 light bulbs
« Reply #46 on: Jul 21st, 2004, 7:04am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: A Prisoner & 100 light bulbs
« Reply #47 on: Jul 21st, 2004, 7:16am » |
Quote Modify
|
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 .
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: A Prisoner & 100 light bulbs
« Reply #48 on: Jul 21st, 2004, 8:01am » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: A Prisoner & 100 light bulbs
« Reply #49 on: Jul 21st, 2004, 8:08am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print