|
Another math problem for you guys. As a side note, is it just me or are prisoners a popular choice for these kind of problems?
There are 100 prisoners in a room. It has been decided by the judge that their fates will be based on a game of luck. The rules of the game are as follows.
There is another room with 100 boxes in a line. Each box contains exactly one piece of paper with the name of one of the prisoners written on it. In some arbitrary order, the prisoners enter the room one at a time and proceed to open 50 of the boxes, in search of their own name. If a prisoner finds his name within 50 box openings, he has succeeded.
If all of the prisoners succeed in finding their own name, then they all get to live. However, if even one person fails to find their name, it's the death penalty for all of them.
The prisoners get to discuss beforehand what strategy they want to use, but there is no communication allowed after the game has begun.
If all the prisoners were to randomly pick 50 boxes, then the total survival chance of the group is (1/2)^100, which is laughably small. The question is, can you devise a strategy for the prisoners that at least grants then some reasonable chance of survival? What is their probability of survival under your strategy?
Points of clarification
-Every prisoner's name appears in exactly one box. There's no case of a prisoner's name being in two boxes.
-There is no swapping of papers among boxes or writing stuff on the paper, or anything that changes the papers or the boxes. The room of boxes is in the exact same state for every prisoner.
As a final note, I do know the solution strategy, but I do not know exactly what the probability of survival is. If you want a ball park figure as a hint:
+ Show Spoiler +
|
After a prisoner opens a box with his name on it, does it get closed and stay in the line of boxes?
|
Yes, everything in the room remains unchanged.
|
ahh I dont get it. If theres no communication allowed then what does it matter what strategy they use? hmmmmm
|
I have two theories, one that will simply remove the possibility of randomness hurting their chances, and one that furthers the first theory so that, assuming success of prisoners before them, each prisoner is picking the fifty boxes most likely to hold their name.
Theory #1
+ Show Spoiler +Prisoner #1 picks boxes 1-50, Prisoner #2 picks boxes 2-51, prisoner #3 picks boxes 3-52, and so on, so that prisoner #100 will pick box 100 and boxes 1-49. This removes the possibility that through randomness a large amount of prisoners will choose the same box or boxes incorrectly over and over again.
Theory #2
+ Show Spoiler +As far as I know, there are a large number of ways to do this, each with equal probability of success, but the theory holds true for each of them, so I will just explain one of them. Prisoner #1 picks boxes 1-50. Since we are assuming that prisoner #1 was successful, prisoner #2 now assumes that of boxes 1-50, one of them is sure not to hold his name, so he therefore is best to pick boxes 51-100. I believe that prisoner #3, assuming success of prisoners 1 & 2, knows that his name is not in one box from boxes 1-50, and not in one box from boxes 51-100, so he would be best to choose the same as prisoner #1, so that Prisoner #4 may choose the same boxes as Prisoner #2, and so on. So basically, even prisoners choose 51-100, and odd prisoners choose 1-50.
I am pretty sure I am completely wrong, but I am relatively certain that both of my strategies have a better probability of success than random choosing. Somebody please explain if I was on the right track.
P.S. - I love these blogs. I love trying to come up to solutions for problems.
|
Oh snap I don't have the time to try this right now, but it's very similar to a different problem I have [: I'll post it up soon and perhaps get back to solving this. Good one though n_n.
|
Doesn't fit exactly with "everything in the room remains unchanged":
+ Show Spoiler +It says they enter the room, but it doesn't say they leave. Stand on one side of the line of boxes if you want the next prisoner to check the first 50 boxes, and the other side if you want him to check the last 50? Decision based on whether you found his name in the 50 you checked first.
Assuming they do enter in this arbitrary order, and that all the prisoners know that order and each others' names.
50% chance of survival.
|
I was assuming that they left the room when they were done, but I am not totally sure now. Slithe?
|
Are the people who go in allowed to move any boxes or do anything besides checking 50?
|
These kind of problems make me feel stupid.
I really have no solid idea on this.
|
I think there is a real solution to this that isn't some sort of trick like staying in the room or moving shit, if you get what I mean. It's always like that.
|
On January 31 2008 03:53 fonger wrote:Doesn't fit exactly with "everything in the room remains unchanged": + Show Spoiler +It says they enter the room, but it doesn't say they leave. Stand on one side of the line of boxes if you want the next prisoner to check the first 50 boxes, and the other side if you want him to check the last 50? Decision based on whether you found his name in the 50 you checked first.
Assuming they do enter in this arbitrary order, and that all the prisoners know that order and each others' names.
50% chance of survival.
That would be "communication" I thought. If they can communicate in anyway its 50%.
But its a pretty clever way of communicating.
On January 31 2008 03:44 Lemonwalrus wrote:I have two theories, one that will simply remove the possibility of randomness hurting their chances, and one that furthers the first theory so that, assuming success of prisoners before them, each prisoner is picking the fifty boxes most likely to hold their name. Theory #1 + Show Spoiler +Prisoner #1 picks boxes 1-50, Prisoner #2 picks boxes 2-51, prisoner #3 picks boxes 3-52, and so on, so that prisoner #100 will pick box 100 and boxes 1-49. This removes the possibility that through randomness a large amount of prisoners will choose the same box or boxes incorrectly over and over again. Theory #2 + Show Spoiler +As far as I know, there are a large number of ways to do this, each with equal probability of success, but the theory holds true for each of them, so I will just explain one of them. Prisoner #1 picks boxes 1-50. Since we are assuming that prisoner #1 was successful, prisoner #2 now assumes that of boxes 1-50, one of them is sure not to hold his name, so he therefore is best to pick boxes 51-100. I believe that prisoner #3, assuming success of prisoners 1 & 2, knows that his name is not in one box from boxes 1-50, and not in one box from boxes 51-100, so he would be best to choose the same as prisoner #1, so that Prisoner #4 may choose the same boxes as Prisoner #2, and so on. So basically, even prisoners choose 51-100, and odd prisoners choose 1-50. I am pretty sure I am completely wrong, but I am relatively certain that both of my strategies have a better probability of success than random choosing. Somebody please explain if I was on the right track. P.S. - I love these blogs. I love trying to come up to solutions for problems.
This is the one I thought of too, but it doesn't improve their chances anywhere remotely near to 20%. Its a tiny improvement. Every other prisoner gets no improvement at all from a 50% success rate, and the other prisoners get 50.5%. lol.
|
I like the other prisoner problem better
|
I did a little searching and found the actual answer. First of all, it is a bit above 30% survival possibility, and it is pretty beautiful imo. If you guys need me to I can link it, but I would be very impressed if somebody got it themselves.
|
1. Do prisoners know each others names?
2. Do they know who is entering after them? Before them?
3. Do they enter immediately after the previous entrant?
+ Show Spoiler +My third question is aimed at a strategy that would include counting to 30 Mississippi in unison (as practice in their strategy making, and then to themselves during the "game"). That way they have a fixed amount of time that they all know would be accurate. One idea I had is something along the lines of starting to count as soon as you open the box, continue counting as you look at the name, and at 30 Mississippi you open the next box, and repeat. This would give the prisoners after the first a reasonable idea where his box is, based on which strategy they choose. If they agree to look 1-50, for example, if he leaves in 10 minutes and 10 seconds (20 counts of 30 Mississippi, 10 seconds to enter the room and get to the first box) then it is obvious his box was #20 and no one should check it after him. This isn't final, just a thought piece that could be expanded if they do enter immediately.
|
On January 31 2008 04:31 Lemonwalrus wrote:
I did a little searching and found the actual answer. First of all, it is a bit above 30% survival possibility, and it is pretty beautiful imo. If you guys need me to I can link it, but I would be very impressed if somebody got it themselves.
Good, then you can tell people if their strategies are getting anywhere or not xD. And perhaps answer questions by saying relevant/irrelevant if a yes/no is not possible.
|
The prisoners know each others names, but they do not know who entered before or after them. I like your strategy, but it is not the correct one. (well, it isn't the one given with the problem)
|
hmm, I'm struggling with this one... I cant really find any better ideas than the ones mention. Trying a brute force method now, but I saw the 20% spoiler and I think I can prove that that kinid of survival probabilys are impossible by using a best case scenario:
Fist guys probability is 50%. No way around that.
Second guy's best shot (for himself alone) is clearly to take the other 50 boxes, in which case he will get 50/99.
Best possible case for third guy is if he knows that the two first guys names NOT were in his boxes. This is clearly not possible to combine with maximising second guys chances, but this is an upper bound. So third guys chances are AT BEST 50/98.
Similarly forth guy will have at best 50/97 until 50:th guy that at best know that the previous 49 guys names are in the other boxes, and he'll get 50/51. guy number 51 and abova can all be guaranteed (in best case for them alone) to pick the right boxes.
So total, if we take maximum survival probability for each person to survive, which is clearly not accievable, we get:
50/100 * 50/99 * 50/98 * ... 50/51 = 50^50 * 50! / 100! = 2.9.. * 10^(-9)
So either my best case calculation is flawed, or the estimate of 20% is way of. 
I'll go work on the brute force a bit more now. :/ let you know if i find anything.
|
On January 31 2008 04:36 Lemonwalrus wrote:
The prisoners know each others names, but they do not know who entered before or after them. I like your strategy, but it is not the correct one. (well, it isn't the one given with the problem)
Haha thanks. Back to the scratchpad xD.
|
could you put a link in a spoiler for the curious ones? =)
(or just pm me ^^)
|
|
|
|
|
|
EPT
