国王和100个囚犯
http://www.iteye.com/topic/569275
?
A simple google on "100 prisoners riddle" yields the following two insights:
?
http://www.algonet.se/~ug/projects/lightbulb/
http://www.ocf.berkeley.edu/~wwu/papers/100prisonersLightBulb.pdf
?
The second one is a pdf, which I appended here.
?
In the above links, I believe they assume the initial state of the light bulb is off, not unknown. They mentioned two ways to do this. The first way has expected value 28... years and the second one has 12.. years. (We can only talk about expected value since the process is a random process.)
?
If the initial state is not known, the strategy for the known case won't work.
?
Assume C is deonted for the counter, and P for other prisoners. Denote X for off and V for on
?
We can just consider 2 prisoner case, where one of them is counter
?
Initial state ?progress
X ? ? ? ? ? ? ? ? ?CP(V)C(X+1) ----> counter is now 1, we can get out
?? ? ? ? ? ? ? ? ? ?P(V)C(X+1) ?----->?counter is now 1, we can get out
V ? ? ? ? ? ? ? ? ?C(X+1) ? ? ? ? -----> counter is 1, but P is not out yet <--------- This is where it breaks down.
?? ? ? ? ? ? ? ? ? ?PC(x+1) ? ? ? -----> counter is 1, we can get out
The '+1' means that the counter increment its counter. (V) means turn on switch, (X) means turn off switch
?
In order to overcome the above problem, we have to let every P switch twice.
X ? ? ? ? ? ? ? ? ?CP(V1)P..PC(X+1)C...CP(V2)P...PC(X+1) ------> The counter is now 2, we can get out now
?? ? ? ? ? ? ? ? ? ?P(V1)P..PC(X+1)C...CP(V2)P...PC(X+1)?------> The counter is now 2, we can get out now
V ? ? ? ? ? ? ? ? ?C(X+1)C...CP(V1)P...PC(X+1)?-----> The counter is now 2, we can get out now
?? ? ? ? ? ? ? ? ? ?PC(X+1)C...CP(V1)P...PC(X+1)?-----> The counter is now 2, we can get out now
?
For 100 prisoners, the counter needs to reach 198.?
?
Not sure the expected value of this method, and not sure we could make it faster using a similar method in the first link.
