Author |
Topic: 5 Prisoners And A Light Bulb (Read 8787 times) |
|
Padfoot
Junior Member
Gender: 
Posts: 129
|
 |
5 Prisoners And A Light Bulb
« on: Jan 29th, 2007, 5:34pm » |
 Quote  Modify
|
See 100 Prisoners and a Light Bulb
What would be the optimal plan for if there were just 5 prisoners?
Is there more than one optimal solution?
  
(They need your help)
|
|
 IP Logged |
"Don't blame me. I'm just an interpreter. I'm not supposed to know a power socket from a computer terminal." - C-3PO, Star WarsV
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #1 on: Jan 30th, 2007, 12:50am » |
Quote Modify
|
I would guess the simple leader solution would be the best bet. More advances strategies probably need more time to pay off.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #2 on: Jan 30th, 2007, 3:02am » |
Quote Modify
|
But the details of how you choose the leader becomes very important.
If for instance the leader is whoever is picked on day 2, he can start with a count of 2 (himself and the first prisoner) with 80% probability or 1 with 20% probability.
If we choose the leader as prisoner of day 3, with a small snowball round, he starts with a count of 3 with 48%, 2 with 32% and 1 with 20%. This is good considering that he otherwise gets an average of less than 1 count in 5 days.
|
| « Last Edit: Jan 30th, 2007, 3:02am by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #3 on: Jan 30th, 2007, 3:47am » |
Quote Modify
|
I don't think those percentages are all quite correct (I get 48,48,4), but I get the idea.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #4 on: Jan 30th, 2007, 4:22am » |
Quote Modify
|
Right. The way I thought of a snowball, a prisoner on day N can pass only 0 or N token by leaving the light off or on. In that case, if the same prisoner is picked on day 1 and 2 he could not pass 2 tokens. He would pass zero. But since the prisoner on day 2 is guaranteed to have at least one token, the meaning of the light off resp. on after day 2 can mean 1 resp. 2 token, instead of 0 and 2. I think on day 3 the same applies.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #5 on: Jan 30th, 2007, 8:52am » |
Quote Modify
|
Along another line, here are what I believe to be optimal strategies for 1 through 4 prisoners (I assign letters to the prisoners based on the order in which they first enter the common room):
1 prisoner and no lightbulb: (optimal)
- Prisoner A enters on day 1, declares success
2 prisoners and no lightbulb: (optimal)
- Prisoner A enters, knows he is A b/c it is day 1, does nothing
- Prisoner B enters, knows he is B b/c it is day >1, declares success
3 prisoners and a lightbulb: (optimal)
- Prisoner A enters, knows he is A b/c it is day 1, turns off the light
- Prisoner B enters, knows he is B b/c it is day >1 and the light is off, turns on the light
- Prisoner C enters, knows he is C b/c it is day >1 and the light is on, declares success
4 prisoners and a lightbulb: (probably optimal)
- Prisoner A enters, knows he is A b/c it is day 1, turns off the light
- Prisoner B enters, knows he is B or D b/c it is day >1 and the light is off, turns on the light
- If prisoner A enters between B and C, he knows either B or D has visited b/c he sees the light on.
- Prisoner C enters, knows he is C b/c it is day >1 and the light is on, turns off the light
- If prisoner A enters between C and D, and he has previously seen the light on, he now knows B and C have visited b/c he sees the light off.
- If prisoner B enters between C and D, he now knows C has visited b/c he sees the light off.
- Prisoner D enters, knows he is B or D b/c it is day >1 and the light is off, turns on the light
- Prisoner A, B or C enters, declares success iff he knows prisoner C has entered.
This gives an average runtime of about three days past when all four prisoners have entered. (C can always declare success on his first visit after D; B has a 50% chance of having entered between C and D and so being able to declare success; A has a 1 in 6 chance.)
I don't see an obvious way to extend this strategy to 5 prisoners, however, as no one but A will know his order for sure.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
CowsRUs
Full Member
Why is it that cats are better then cows? Why not?
Gender:
Posts: 175
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #6 on: Feb 7th, 2007, 5:17pm » |
Quote Modify
|
That's weird... i cant seem to find 100 prisoners and a light bulb at all...
can sum1 post it up here plz?
|
|
IP Logged |
"It is very good to have a brother who has a cow. It is also good to have a brother who has two cows. In fact, a brother with a cow is great, except when he has exactly 135 cows and is one of thecow himself."-Unknown
|
|
|
Padfoot
Junior Member
Gender:
Posts: 129
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #7 on: Feb 7th, 2007, 5:29pm » |
Quote Modify
|
Did you look under the "hard" section?
|
|
IP Logged |
"Don't blame me. I'm just an interpreter. I'm not supposed to know a power socket from a computer terminal." - C-3PO, Star WarsV
|
|
|
CowsRUs
Full Member
Why is it that cats are better then cows? Why not?
Gender:
Posts: 175
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #9 on: Feb 7th, 2007, 5:44pm » |
Quote Modify
|
ok, i thought it was a forum question. thanks
|
|
IP Logged |
"It is very good to have a brother who has a cow. It is also good to have a brother who has two cows. In fact, a brother with a cow is great, except when he has exactly 135 cows and is one of thecow himself."-Unknown
|
|
|
CowsRUs
Full Member
Why is it that cats are better then cows? Why not?
Gender:
Posts: 175
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #10 on: Feb 7th, 2007, 5:51pm » |
Quote Modify
|
i forgot, what is the "leader solution"? I'm guessing is that one person is the "leader" and whenever he goes into the room he turns on a light bulb
|
|
IP Logged |
"It is very good to have a brother who has a cow. It is also good to have a brother who has two cows. In fact, a brother with a cow is great, except when he has exactly 135 cows and is one of thecow himself."-Unknown
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #11 on: Feb 7th, 2007, 6:36pm » |
Quote Modify
|
You can find a thread for the 100 prisoners and a light bulb in the Hard forum.
The leader solution has one prisoner elected as leader. He is the only one who can turn the light off. Everyone else turns on the light exactly once: the first time they enter the room and find the light off. When the leader has turned off the light 99 times (or 4 times or however-many-prisoners-there-are-other-than-him times), he knows that everyone else has entered the room, and he obviously has (at least 99 times), so he declares at this point.
A nice solution, but it can be beat by a factor of 3.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
CowsRUs
Full Member
Why is it that cats are better then cows? Why not?
Gender:
Posts: 175
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #12 on: Feb 7th, 2007, 7:29pm » |
Quote Modify
|
oh nice...
|
|
IP Logged |
"It is very good to have a brother who has a cow. It is also good to have a brother who has two cows. In fact, a brother with a cow is great, except when he has exactly 135 cows and is one of thecow himself."-Unknown
|
|
|
CowsRUs
Full Member
Why is it that cats are better then cows? Why not?
Gender:
Posts: 175
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #13 on: Feb 7th, 2007, 7:29pm » |
Quote Modify
|
If it was up to me, I'd be shot... or so my brother says... 
|
|
IP Logged |
"It is very good to have a brother who has a cow. It is also good to have a brother who has two cows. In fact, a brother with a cow is great, except when he has exactly 135 cows and is one of thecow himself."-Unknown
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #14 on: Feb 9th, 2007, 5:47am » |
Quote Modify
|
It seems to me that one counter with snowroll prephase should be optimal for this case. One should just check whether the 4 days prephase is optimal or 3 days is better.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #15 on: Feb 10th, 2007, 6:56am » |
Quote Modify
|
OK, 3 days snowroll gives 24,776666666... average.
(whoever turns light off becomes counter ...
first day do nothing, second day turn light off if you were here first day, otherwise turn it on, third day if the light is off do nothing, otherwise if you were here already turn it off, fourth day if the light is on, turn it off and do nothing, otherwise if you were not here with light on during first three days and didn't turn light on yet, turn light on. If you became counter, turn light off whenever is on.
If you became counter on day d<=4 when you were 2nd times near the bulb, declare success with the (5-d+2)-th switch off. If you became counter on day 4 during your first visit, declare success with the 2nd =(5-4+1) swith off (including the declaration swith off).)
2 days snowroll gives 25,2166666
4 days snowroll gives 25,3926666
So the 3 days is optimal choice.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #16 on: Feb 10th, 2007, 11:05am » |
Quote Modify
|
It's always possible to guarantee that the person entering on day 3 has complete information, so given that a 3-day snowball is the optimum length snowball for the 5 prisoner game, doing a special 3-day leader picking must be better than any snowball.
I'm not about to produce a simulation to get numbers, but the following should perform better:
Day 1: do nothing
Day 2, repeat visit: turn light off
Day 2, new prisoner: turn light on
Day 3, repeat visit: turn light off and start with count of 1 or 2 depending on whether someone else has been in
Day 3, new prisoner: turn light off and start with count of 2 or 3 depending on whether the light was off or on.
Anyone who didn't visit during the first 3 days turns the light on at the next opportunity; the prisoner who visited on day 3 turns it off at every opportunity and keeps count.
As a further improvement, on day 3, the light can be left on either to signal a count of 2, or ((see below)) to signal a count of 3 (I'm not sure which would work better) and the prisoner entering on day 4 then becomes a "watcher" - after leaving the light off on day 4 if they had been in before, or on if they hadn't, they then don't touch the switch, but keep track of observed changes in the bulb state between visits - so if the signalled count were 3, and the watcher were the fourth prisoner, then if he saw the light off on a subsequent visit, he'd know he'd been counted, and there was one prisoner left to turn the light on - so seeing the light on again would let him claim victory.
It's possible for the watcher to miss a count entirely (if the light is switched twice or more between consecutive visits) so there's no guarantees he'd be helpful, but it costs nothing to use the light on the third day to create one since it's otherwise unused...
Some quick calculations suggest that it's best to use the bulb to signal a count of 3 on day 3 - if the prisoner on day 4 is a repeat entry, they'll get complete information from a signal of 2 or 3. A new prisoner would get a signal of 2 in 36/125 trials and a signal of 3 in 24/125 trials, but the new prisoner starting from a count of 3 (including themself) would only have a 1/12 chance of not missing a count (or a 1/24 chance of getting to claim freedom) while a new prisoner starting with a count of 4 has a 1/4 chance of not missing a count (or a 1/8 chance of being the one to claim freedom)
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #17 on: Feb 12th, 2007, 2:40pm » |
Quote Modify
|
rmsgrey: very nice trick, reducing probability of snowroll initialisation to 1 from 1/n to 1/n^2 for n prisoners. ... such 2 day snowroll without watcher gives 24.21666 average, and 3 day snowroll with 2nd day exception gives 23,776666 average.
I should correct your calculations ... with 1/25 probability counter is initialised to 1, with 12/25 is initialised to 2, with 12/25 the snowroll is not finished yet. ... it seems to be better to propagate the latter info and no watcher is needed.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #18 on: Feb 12th, 2007, 2:56pm » |
Quote Modify
|
Probably my notation of snowroll length is a bit confusing ... k-day snowroll in my notation means k-th night is the last night with snowroll signalling.
The exception of course is in 3rd day. And can be applied on snowrolling in general for n-prisoners.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #19 on: Feb 13th, 2007, 10:21am » |
Quote Modify
|
So your earlier figures for 2, 3 and 4 day snowballs apply to the prisoner entering on the 3rd, 4th and 5th day respectively becoming counter when a different prisoner enters each day?
In that case, with the prisoner entering on the fourth day becoming the counter in 12/25 cases, (24/125 with a count of 4; 36/125 with a count of 3), and the prisoner entering on the third day becoming counter in the remaining cases (1/25 count of 1; 12/25 count of 2), there are two choices for what to do with the bulb on day 4 - either use it to signal a potential watcher (which is useful when the counter is chosen on day 4) or use it as the first signal of the ongoing counting process (which is useful when the counter is chosen on day 3)
There's still scope for watchers to save time in bad cases - non counters become watchers with a worst-case count and occasionally have the right count and manage not to miss any signals (a 9/250 (36/125 of the right count, 1/4 of not missing intervening signals and 1/2 of intercepting the final signal) chance of the prisoner who entered on the third day successfully claiming release as a watcher - other prisoners have worse odds)
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #20 on: Feb 14th, 2007, 7:36am » |
Quote Modify
|
Yes; with 3 day snowroll in my terminology, 4th night uses "token" signaling (if the counter was choosen on 4th day, it is off, otherwise it can signal new prisoner entered).
I didn't calculate average 'time' for watcher method yet ... I am planning to calculate it, but it is harder case ;( ... I am not sure I can do it analytically. At least it can be aproximated by some kind of dynamic programming. ... I need to improve the method required for more general case ... observers method called in my terminology.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #21 on: Feb 14th, 2007, 2:40pm » |
Quote Modify
|
My doubts were not confirmed. For one phase algorithms we don't need to know probabilistic distribution and computing average 'time' is easy by following recurent formulas:
T+g,n,p = 5/(n+1)+n/(n+1)T + g,n-1,p+1 + 1/(n+1)T-g-1,0,p,
T-g,n,p = 5/(p+g)+p/(p+g)T-g,n+1,p-1 + g/(p+g)T+g,n,0, T-0,n,p = 0, T+1,n,1 = 0.
where superscript denotes light on/off, g is the counter goal, n+p is the number of observers able to finish the process, p are those of them who have seen light on during the last visit. For our case p+n<=1 so it is much easier.
... results will be soon  ... the improvement in 3 days snowroll by observers is 0.12 when counter starts with goal of 2. Some smaller improvement is also when he starts with higher goal.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #22 on: Mar 7th, 2007, 7:19am » |
Quote Modify
|
Finaly the computation is finished ... it takes 3 pages after shortening ... improvement of observers in single counter method with n prisoners, snowroll of length s with 2/3 day hook is:
(12n2-20n+10)/(2nn!)-(63 2n-5)/(3nn!(n-1)!)+
18/(6nn!(n-1)!)+ sk=3 n!(k-1)/(2n-knk+1(n-k)!(n-k)!).
This is of order 10-128 for n=100,s=28 and 0.07859828 for n=5, s=3.
I hope there is no bug in computation, the most challenging part was not yet counted observers with full info (first three days the same prisoner choosen).
In my previous post the result should be 0.024 ... I missed one division by 5 somehow. 
So the resulting best (at least so far) algorithm for 5 prisoners gives average approx 23,69806838.
|
| « Last Edit: Nov 4th, 2008, 3:23pm by Hippo » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #23 on: Nov 13th, 2008, 1:54pm » |
Quote Modify
|
on Feb 10th, 2007, 6:56am, Hippo wrote:OK, 3 days snowroll gives 24,776666666... average.
(whoever turns light off becomes counter ...
first day do nothing, second day turn light off if you were here first day, otherwise turn it on, third day if the light is off do nothing, otherwise if you were here already turn it off, fourth day if the light is on, turn it off and do nothing, otherwise if you were not here with light on during first three days and didn't turn light on yet, turn light on. If you became counter, turn light off whenever is on.
If you became counter on day d<=4 when you were 2nd times near the bulb, declare success with the (5-d+2)-th switch off. If you became counter on day 4 during your first visit, declare success with the 2nd =(5-4+1) swith off (including the declaration swith off).)
2 days snowroll gives 25,2166666
4 days snowroll gives 25,3926666
So the 3 days is optimal choice. |
|
Actually I were pesimistic here ... if the counter was choosen before the last snowroll night, the following night may be used for counter signalling. This reduces the probabilities following way:
2 nights snowroll gives 25,0166667
3 nights snowroll gives 24,2566667
4 nights snowroll gives 24,5846667
2nd night hook improves it by one day.
Observer(s) improve it by a very small amount.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 5 Prisoners And A Light Bulb
« Reply #24 on: Apr 14th, 2009, 1:04pm » |
Quote Modify
|
So one leader with snowball is not optimal for 5 prisoners.
Ignoring first and binary scheme (with observers) with all phase lengths 16 has average around 22,9 days.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print