Author |
Topic: 100 PRISONERS AND A LIGHT BULB (Read 1156 times) |
|
casual_kumar
Newbie
Gender: 
Posts: 21
|
 |
100 PRISONERS AND A LIGHT BULB
« on: Aug 7th, 2006, 12:48am » |
 Quote  Modify
|
They will choose a leader among themselves and below if the strategy.
If the leader visits the room and finds the buld switched on, he switches it off and increments the count. (he remembers how many times he switched off the bulb)
If any one except the leader visits the room then he witches the bulb on if and only if the bulb is not already on and it will be his first change to the switch (he may have visited the room earlier but did not do anything because the bulb was already on !!) Otherwise, he will choose not to change the status of the switch.
the bottom line is that, every non-leader switches the bulb ON only once and the leader switches the bulb OFF everytime someone else switches it on.
So, he declares that they all have visited the bulb room atleast once if his count equals 99.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 100 PRISONERS AND A LIGHT BULB
« Reply #1 on: Aug 7th, 2006, 2:54am » |
Quote Modify
|
Have you also looked at the average runtime of this method? I think it was more than a lifetime.
If you check the older thread (and dig really hard) you can find some much faster methods. (Here's the start of a summary)
|
| « Last Edit: Aug 7th, 2006, 3:08am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: 100 PRISONERS AND A LIGHT BULB
« Reply #2 on: Aug 8th, 2006, 10:28am » |
Quote Modify
|
on Aug 7th, 2006, 2:54am, towr wrote:Have you also looked at the average runtime of this method? I think it was more than a lifetime.
If you check the older thread (and dig really hard) you can find some much faster methods. (Here's the start of a summary) |
|
Actually, that method was quite reasonable, with an expected run time a little under 30 years. There were much worse behaviours (~150 years) and some better ones - the best performance being between 9 and 10 years if I remember correctly...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 100 PRISONERS AND A LIGHT BULB
« Reply #3 on: Aug 8th, 2006, 10:38am » |
Quote Modify
|
on Aug 8th, 2006, 10:28am, rmsgrey wrote:| the best performance being between 9 and 10 years if I remember correctly... |
|
3.5-4 years or so, I think.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: 100 PRISONERS AND A LIGHT BULB
« Reply #4 on: Aug 8th, 2006, 10:58am » |
Quote Modify
|
Erm, no.  The best strategy so far discussed has an average runlength of 3460 days or just under 9.5 years. All the prisoners will have visited the room in, on average, 1.42 years, so a runlength of only 3.5 - 4 years would be truly remarkable!
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
capricafox
Newbie
Gender:
Posts: 8
|
|
Re: 100 PRISONERS AND A LIGHT BULB
« Reply #5 on: Aug 9th, 2006, 7:30pm » |
Quote Modify
|
(about the variant with 2 or N light bulbs in unknows initial state)
First, getting rid of the unknown state:
if a prisoner could know he is the first to visit, he flicks all bulb off. And then it's like he never visited.
Otherwise, only the leader can flick off the switches (what a waste of time).
After that, you can assume simply that every time the leader comes back, he may increment by up to N the number of prisoners that visited.
Alternately, there could be a natural ordering which could provide a "bitset" to count every bulb as a distinct power of 2 (with 3 bulbs you could count up to 7) which speeds up the counting by the leader.
You could imagine that N bulbs with N leaders and N pools or prisoners could go faster, but eventually your pools could be unbalanced you could end up with ~32 prisonners on the same single bulb. I don't know the math to find the fastest way.
One last trick: let's say 10 bulbs. Leave 1 bulb for a counting "mode". In mode "off", the leader counts as usual. In mode "on", the 9 other bulbs are now simple flags cleared by the leader. The flag mode is only enabled when there are 9 prisoners or less to visit. From then on, any one visiting that sees all 9+1 bulbs on is able to declare they all visited. (basically the leader told everyone therewas 9 left by flicking the mode bulb on)
And of course, for a 100 bulbs, there is no problem...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print