wu :: forums - Print Page


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

        riddles >> hard >> 100 PRISONERS AND A LIGHT BULB
        
(Message started by: casual_kumar on Aug 7^th, 2006, 12:48am)

Title: 100 PRISONERS AND A LIGHT BULB
Post by casual_kumar on Aug 7^th, 2006, 12:48am

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.

Title: Re: 100 PRISONERS AND A LIGHT BULB
Post by towr on Aug 7^th, 2006, 2:54am

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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027805293;start=375#382)'s the start of a summary)

Title: Re: 100 PRISONERS AND A LIGHT BULB
Post by rmsgrey on Aug 8^th, 2006, 10:28am

on 08/07/06 at 02:54:53, towr wrote:

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...

Title: Re: 100 PRISONERS AND A LIGHT BULB
Post by towr on Aug 8^th, 2006, 10:38am

on 08/08/06 at 10:28:58, rmsgrey wrote:

the best performance being between 9 and 10 years if I remember correctly...

3.5-4 years or so, I think.

Title: Re: 100 PRISONERS AND A LIGHT BULB
Post by SMQ on Aug 8^th, 2006, 10:58am

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

Title: Re: 100 PRISONERS AND A LIGHT BULB
Post by capricafox on Aug 9^th, 2006, 7:30pm

(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...