Author |
Topic: A Prisoner & 100 light bulbs (Read 2541 times) |
|
Padzok
Junior Member
Gender: 
Posts: 104
|
 |
Re: A Prisoner & 100 light bulbs
« Reply #50 on: Sep 8th, 2004, 4:37pm » |
 Quote  Modify
|
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. 
I believe the guy has like total recall. If not, then do not bother reading the answer, just tell me I am wrong.
::
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.
::
So (a) does my suggestion work? and (b) how far from the ideal is it?
|
| « Last Edit: Sep 8th, 2004, 11:23pm by Padzok » |
 IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: A Prisoner & 100 light bulbs
« Reply #51 on: Sep 9th, 2004, 5:07am » |
Quote Modify
|
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(n2 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.
|
|
IP Logged |
|
|
|
Padzok
Junior Member
Gender:
Posts: 104
|
|
Re: A Prisoner & 100 light bulbs
« Reply #52 on: Sep 9th, 2004, 2:53pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: A Prisoner & 100 light bulbs
« Reply #53 on: Sep 9th, 2004, 3:30pm » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print