Author |
Topic: 100 anonymous prisoners & a light bulb (Read 2529 times) |
|
yegulalp
Newbie
Gender: 
Posts: 7
|
 |
100 anonymous prisoners & a light bulb
« on: Jul 15th, 2005, 2:08am » |
 Quote  Modify
|
Here is an interesting new variation of the prisoners and light bulb madness. I believe I have a solution, but is almost certainly not optimal.
As a representative of Amnesty Intergalatic, you are the first human to land on planet Xorg. The Xorg Emperor has a special prison with 100 Xorgian inmates, whose identities are deliberately kept secret, even from each other. They are all innocent, but kept prisoner for life by the Emperor to demonstrate his power. Xorgians are naturally imortal, so these poor slobs have a lot of time on their hands.
You amuse the Emperor, so he grants your request to give the prisoners a chance to free themselves. This is the game:
1) You may write any instructions you wish on a piece of paper.
2) The jail warden will have 100 copies made of your instructions, with one given to each prisoner.
3) Thereafter, the warden will at random time intervals choose a random prisoner and take him to an empty closet with a light bulb. The prisoner is free to turn the bulb on or off as he likes, but can do nothing else. Then the prisoner will be taken back to his cell.
4) There is only one such closet in the prison. The light bulb is Xorgian, so it is guaranteed never to burn out. The light bulb is currently off.
5) The prison cells are windowless and soundproof. (And Xorgians do not have power to see through walls, etc.). The prisoners cannot communicate in any way, except by turning the bulb on and off.
6) At any point, any prisoner can claim that they have all visited the closet at least once. If he is right, all the prisoners will be freed. If he is wrong, the game is lost, the prisoners will never be released, and they will enjoy a daily dose of Xorgian torture for the (infinite) remainder of their sentences.
What should your instructions be to guarantee that the inmates will be freed with probability 1? Xorgians are fearful of uncertainty (and torture), no matter how small, so they will only follow a plan if it guarantees that they cannot lose the game. Since they are immortal, it matters little if the plan takes a while to unfold.
For those who are familiar with the standard prisoners/light bulb puzzle, the key differences are:
1) The prisoners do not meet
2) They must all follow the same algorithm, since they all get the same instructions
3) The visits are at random intervals instead of once a day. This ruins the utility of plans where prisoners do things according to the day number.
CORRECTION: In my original post, I forgot to include the stipulation that the light is currently off. It can be solved without that constraint, as shown by the first few people responding.
|
| « Last Edit: Jul 16th, 2005, 12:19pm by yegulalp » |
 IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2872
|
|
Re: 100 anonymous prisoners & a light bulb
« Reply #1 on: Jul 15th, 2005, 6:55am » |
Quote Modify
|
I'm not aware of any solution type that fits these conditions. If you have one that will work, I'd be very interested to hear it.
Edit - As subsequent posts show, there is indeed a solution type that works (and I was interested when I heard it - once I stopped hitting myself over the head for missing it)
|
| « Last Edit: Jul 17th, 2005, 5:09am by rmsgrey » |
IP Logged |
|
|
|
yegulalp
Newbie
Gender:
Posts: 7
|
|
Re: 100 anonymous prisoners & a light bulb
« Reply #2 on: Jul 15th, 2005, 8:42am » |
Quote Modify
|
I will post my solution tomorrow. I want to give people some time to see the original posting without a solution.
|
|
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: 100 anonymous prisoners & a light bulb
« Reply #3 on: Jul 16th, 2005, 1:51am » |
Quote Modify
|
"Use the virtual token model where turning the bulb on/off equates to depositing/withdrawing a token from the room. Start with an inventory of 2 tokens. Declare success whenever you have 200 tokens. Whenever leaving the room, leave a token there iff you have made an even number of total visits (and a token is available). Donate to your local Amnesty Intergalactic branch and support truly universal sapient rights."
Running time: I hope Xorgians can survive a heat death of the universe.
|
| « Last Edit: Jul 16th, 2005, 9:43am by Rezyk » |
IP Logged |
|
|
|
yegulalp
Newbie
Gender:
Posts: 7
|
|
Re: 100 anonymous prisoners & a light bulb
« Reply #4 on: Jul 16th, 2005, 7:34am » |
Quote Modify
|
I think Rezyk's solution works, but I have a couple of clarifying questions:
1) When do people take tokens? Whenever possible, except if they are on an even visit?
2) Why not just start with 1 token and finish with 100? I don't see why 2 is needed. It also makes it much slower.
|
| « Last Edit: Jul 16th, 2005, 7:36am by yegulalp » |
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: 100 anonymous prisoners & a light bulb
« Reply #5 on: Jul 16th, 2005, 9:32am » |
Quote Modify
|
1) correct
2) Note that in your proposed method, you have 101 tokens in the pool if the bulb starts on.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 anonymous prisoners & a light bulb
« Reply #6 on: Jul 16th, 2005, 10:20am » |
Quote Modify
|
A slightly improved version now that I've got my brain working again...
| hidden: | 1) Start with two tokens. If the light is on when you enter the closet, gain a token. If the light is on when you leave the closet, lose a token.
2) If you have no tokens, you cannot leave/turn the light on.
3) If you have more than 100 tokens, you can never leave/turn the light on.
4) If you have 200 tokens, declare victory.
5) If the light was off the first time you entered the closet, or you have ever had 0 tokens, you must leave/turn the light on whenever you have a token available.
6) Otherwise, leave/turn the light on on even-numbered visits, and off on odd-numbered visits until you satisfy the conditions for rule 3 or rule 5. |
Running time should beat Rezyk's by a considerable margin by using the loss of symmetry amongst prisoners much earlier in the process.
|
|
IP Logged |
|
|
|
yegulalp
Newbie
Gender:
Posts: 7
|
|
OOPS!
« Reply #7 on: Jul 16th, 2005, 12:14pm » |
Quote Modify
|
Sorry guys, I meant to include the stipulation that the LIGHT STARTS IN THE "ON" POSITION. However, you've ably demonstrated that it can be solved without that information. I'll edit my original post to fix the mistake.
|
|
IP Logged |
|
|
|
yegulalp
Newbie
Gender:
Posts: 7
|
|
Simplest solution
« Reply #8 on: Jul 16th, 2005, 1:56pm » |
Quote Modify
|
This is the simplest (and slowest) solution for the corrected version of the puzzle (light starts in off position).
Solution for N prisoners:
Every prisoner follows the same instructions:
1) You start with token count c = 1
2) If the light is on, turn it off and set c = c+1
3) If the light is off AND c>0, turn the light on and set c = c-1
4) If you ever reach c=N, you can be sure everyone has visited the closet.
Numerical experiments show that this works, but is VERY slow.
N=5, mean time is 305 visits (10,000 Monte Carlo trials)
N=7, mean time is 3774 visits (10,000 trials)
N=10, mean time is 180,000 visits (100 trials)
N=15, mean time is 64 million visits (1 trial)
N=100, forget it!
|
| « Last Edit: Jul 16th, 2005, 1:58pm by yegulalp » |
IP Logged |
|
|
|
yegulalp
Newbie
Gender:
Posts: 7
|
|
Better solution
« Reply #9 on: Jul 16th, 2005, 1:59pm » |
Quote Modify
|
This is a slightly better solution for N prisoners (light starts in the off position):
1) You start with token count c = 1
2) If the light is on AND c>0, turn it off and set c = c+1
3) If the light is off AND 0 < c <= N/2, turn the light on and set c = c-1
4) If you ever reach c=N, you can be sure everyone has visited the closet.
Numerical experiments show this is vastly better than the simplest version:
N=5, mean time is 33.8 visits (10,000 trials)
N=15, mean time is 522 visits (10,000 trials)
N=50, mean time is 12,200 visits (1,000 trials)
N=100, mean time is 79,700 visits (1,000 trials)
|
|
IP Logged |
|
|
|
yegulalp
Newbie
Gender:
Posts: 7
|
|
Fastest solution I know
« Reply #10 on: Jul 16th, 2005, 2:02pm » |
Quote Modify
|
This is the fastest solution I have found for the version where the light starts in the off position:
If we have N prisoners, define:
M = N/2 for even N,
M = (N-1)/2 for odd N.
While the prisoners wait in their cells, they count from 1 to M
over and over until the warden arrives. That selects a random
number R between 1 and M. The rules are:
1) You start with token count c = 1
2) If the light is on and R <= c, turn it off and set c=c+1
3) If the light is off and R >= c > 0, turn it on and set c=c-1
4) If you hit c=N, you can be sure everyone has been to the closet.
Basically, I've modified the previous solution by making the transition random, with probabilities linearly varying with c. You might think that we could do better than a linear function, but surprising ly every other function I've tried is worse. Any ideas on that?
Numerical results:
N = 5, mean time is 36 visits (10,000 trials)
N = 15, mean time is 508 visits (10,000 trials)
N = 50, mean time is 7,300 visits (1,000 trials)
N = 100, mean time is 32,600 visits (1,000 trials)
So it'a actually slightly slower for very small N, but
quite a bit better by N=100.
|
| « Last Edit: Jul 16th, 2005, 2:05pm by yegulalp » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 anonymous prisoners & a light bulb
« Reply #11 on: Jul 17th, 2005, 5:32am » |
Quote Modify
|
Apart from the whole known initial bulb state issue, yegulalp'ssolution is reassuringly close to mine - the other significant difference is:
| hidden: |
Both of us have those with up to 1 token (including the lit bulb) be totally generous (always pass tokens if possible) while those with more than half the tokens are totally greedy (always collect any available tokens), but I used a constant average greediness between those two extremes, while yagulalp's solution has a linear function making greed a continuous function of proportion of available tokens held.
The only type of function that I think might improve on a linear increase would be something like:
P(greedy) = (1-cos(PI*c/(M+1)))/2
which, if I've got my scaling correct, gives a nice half sine wave going from 0 at c=0 to 1 at c=M+1 |
I've no idea whether that suggested tweak will improve things or not. It's about the only thing I can think of that would plausibly improve on linearity.
|
|
IP Logged |
|
|
|
RiverPhoenix
Guest
|
|
Re: 100 anonymous prisoners & a light bulb
« Reply #12 on: Jul 17th, 2005, 7:31pm » |
Quote Modify
 Remove
|
If the only degree of freedom is the greediness factor for each number of tokens owned, then there might actually be an optimality proof for this problem.
Does a multi-stage approach improve times here, given that 'extra tokens' cannot be given out before the round?
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 anonymous prisoners & a light bulb
« Reply #13 on: Jul 18th, 2005, 3:01pm » |
Quote Modify
|
on Jul 17th, 2005, 7:31pm, RiverPhoenix wrote:If the only degree of freedom is the greediness factor for each number of tokens owned, then there might actually be an optimality proof for this problem.
Does a multi-stage approach improve times here, given that 'extra tokens' cannot be given out before the round? |
|
The problem with multi-staging is that you can't tell how long the light has been left on - if you enter the room for the first time since the second stage began, and the light is on, how can you tell whether it was turned on during the first stage and you're the first to visit since then, or it was turned on during the second stage, and has the different meaning?
Effectively, every time you change stage, you have a chance to convert a previous-stage token into a new-stage token, confusing the count for each. If the second stage uses tokens each representing 10 first-stage tokens, then, when the second stage starts, you could have converted a 1-token into a 10-token - so you could have up to 9 prisoners who have never visited being counted unless you increase the total number of tokens to compensate - meaning you're needing to count to 991 of 1000 counters - and that's before you look at what happens if the first stage failed and you have to repeat it later - the stage 2 to stage 1 transition potentially destroys 9 counters, pushing the potential error up to 18, or 27 by the time stage 2 repeats and you have another chance to claim vistory, so either each prisoner has to get an additional 18 counters as you start the repeat, or you have to abandon all previous progress and start again from scratch (obviously better)
I suppose it's possible that a multi-stage process could have a good enough performance to bring down the expected run time enough to compensate for the large increase in number of counters and the periodic reset, but you stil need to know somthing about the average frequency of visits in advance in order to choose your stage lengths - if you're resetting every third visit (on average) you're never going to get out, while having a first stage of a million visits is going to be significantly slower than the simpler methods.
|
|
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: 100 anonymous prisoners & a light bulb
« Reply #14 on: Jul 18th, 2005, 8:35pm » |
Quote Modify
|
on Jul 18th, 2005, 3:01pm, rmsgrey wrote:| I suppose it's possible that a multi-stage process could have a good enough performance to bring down the expected run time enough to compensate for the large increase in number of counters and the periodic reset, but you stil need to know somthing about the average frequency of visits in advance in order to choose your stage lengths - if you're resetting every third visit (on average) you're never going to get out, while having a first stage of a million visits is going to be significantly slower than the simpler methods. |
|
Even if you don't know, you could get tricksy and make each stage twice as long as the previous one (and work that backwards such that an infinite number of stages pass in the first second).
Phrased another way: New stage whenever log2t is an integer.
|
| « Last Edit: Jul 18th, 2005, 8:45pm by Rezyk » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: 100 anonymous prisoners & a light bulb
« Reply #15 on: Jul 19th, 2005, 7:50am » |
Quote Modify
|
on Jul 18th, 2005, 8:35pm, Rezyk wrote:
Even if you don't know, you could get tricksy and make each stage twice as long as the previous one (and work that backwards such that an infinite number of stages pass in the first second).
Phrased another way: New stage whenever log2t is an integer. |
|
That does solve the problemof stage lengths rather neatly - approximately doubling the expected number of visits to escape.
That still leaves the problem that you're having to collet 100 stage-2 tokens for victory - suggesting that you're better off not bothering with the first stage at all...
(((At the transition between 1-tokens and k-tokens, (k-1) counters may be generated, meaning that everyone has to start with k counters so that anyone who hasn't visited must have more than k-1 counters, so have at least 1 k-token - and have exactly what they started with. So there must always be at least 100 k-tokens in the final count.)))
|
|
IP Logged |
|
|
|
River Phoenix
Guest
|
|
Re: 100 anonymous prisoners & a light bulb
« Reply #16 on: Jul 20th, 2005, 5:09am » |
Quote Modify
Remove
|
Why can't we just have the prisoners always try to collect a token on the day before the stage changes - then the light bulb is off to start the next stage, right?
|
|
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: 100 anonymous prisoners & a light bulb
« Reply #17 on: Jul 20th, 2005, 11:15am » |
Quote Modify
|
In this version of the puzzle, for any given day, there might be no visitors.
|
|
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: 100 anonymous prisoners & a light bulb
« Reply #18 on: Jul 21st, 2005, 6:48am » |
Quote Modify
|
Oh, thanks. I see now why the above few posts make sense. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print