|
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 ^^)
|
On January 31 2008 04:39 Cascade wrote: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. I'm thinking there is a way to eliminate more than 1 box as wrong for each prisoner's specific name for each 1 entrant into the room. In other words, perhaps there is a method that would make the second guy's probability not 50/99 but 50/80, just to give a random number.
And someone else said it's over 30%.
|
Here is the actual answer, please don't read unless you totally give up. Think outside of the box. (sorry, I couldn't resist. ) + Show Spoiler +Last chance, if you turn back now, nobody has to know you were here. + Show Spoiler +
|
On January 31 2008 04:42 fanatacist wrote:Show nested quote +On January 31 2008 04:39 Cascade wrote: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. I'm thinking there is a way to eliminate more than 1 box as wrong for each prisoner's specific name for each 1 entrant into the room. In other words, perhaps there is a method that would make the second guy's probability not 50/99 but 50/80, just to give a random number. And someone else said it's over 30%.
Yeah i must ahve missed something if you get to 30%.
edit2: also better spoiler this, since it may contain a hint... + Show Spoiler +hmm, probably it is the fact that they do not choose all boxes at once, but they open one at a time. Then they can use the name in the first box they open, to choose which box to open afterwards. yeah, that's must be it... brb.
EDIT: I'm NOT READING THAT SPOILER!
|
If they do not know who is going in before/after them, do they at least know if they are first, second, third, etc.?
|
On January 31 2008 04:56 fanatacist wrote: If they do not know who is going in before/after them, do they at least know if they are first, second, third, etc.?
Don't worry, this is only in a spoiler because it kinda gives a hint. + Show Spoiler +I am not sure of the answer to that question, but the best I can tell you is that the answer, whether it be yes or no, is irrelevant.
|
On January 31 2008 05:01 Lemonwalrus wrote:Show nested quote +On January 31 2008 04:56 fanatacist wrote: If they do not know who is going in before/after them, do they at least know if they are first, second, third, etc.? Don't worry, this is only in a spoiler because it kinda gives a hint. + Show Spoiler +I am not sure of the answer to that question, but the best I can tell you is that the answer, whether it be yes or no, is irrelevant. Thanks [:
Very manner problem solvers here! n_n
|
I just know that it feels really good to solve something like this on your own without help.
|
OK, I looked at the solution. Couldn't resist :p
This is only in spoiler in case it gives a hint:
+ Show Spoiler +I would have never have got it, I didn't understand the mathematics behind the explanation, I'll believe it though
|
ok, I think I have found the solution.
+ Show Spoiler +Prisoner number a starts a box number a. He will there find the name of prisoner number b, and he will next open box number b, and so on. This will work as long as there are no "loops" longer than 50 among the boxes. A loop is when you follow boxes with the algorithm above, you will eventually come back to where you started. Which is your number! So as long as you finish one lap in your loop within 50 steps, you're fine. If the loop is longer than 50, everyone with numbers in that loop will fail, which is what correlates the success of the prissoners. and since this is everyone or noone thingy, you want as much correlation as possible. Next thing would be to calculate the probability of not having loops longer than 50. But I wont do that. If this is correct solution, the calculation will be in walrus' spoiler. if im wrong, it wont make snece to calculate it. But 30% sounds plausible at first sight. Then proving that there are no other better strategies... no idea right now. Maybe you can make som smart argument, or it will be very complicated. I'll have a look at the spoiler anyway.
yay, it was right! ^^ + Show Spoiler +And they didnt prove that it was the best strategy, or calculate the probability exactly, which suggest that both are complicated. Which probably forgives my omission of those two...
|
On January 31 2008 06:06 Cascade wrote:ok, I think I have found the solution. + Show Spoiler +Prisoner number a starts a box number a. He will there find the name of prisoner number b, and he will next open box number b, and so on. This will work as long as there are no "loops" longer than 50 among the boxes. A loop is when you follow boxes with the algorithm above, you will eventually come back to where you started. Which is your number! So as long as you finish one lap in your loop within 50 steps, you're fine. If the loop is longer than 50, everyone with numbers in that loop will fail, which is what correlates the success of the prissoners. and since this is everyone or noone thingy, you want as much correlation as possible. Next thing would be to calculate the probability of not having loops longer than 50. But I wont do that. If this is correct solution, the calculation will be in walrus' spoiler. if im wrong, it wont make snece to calculate it. But 30% sounds plausible at first sight. Then proving that there are no other better strategies... no idea right now. Maybe you can make som smart argument, or it will be very complicated. I'll have a look at the spoiler anyway. Don't readify my spoiler if you haven't solved it yet, gives away whether he was right or not. + Show Spoiler +You are my hero.
|
If you knew whether you were second or first, this would be my guess (expanded inductively, obv.): + Show Spoiler +Assume 4 boxes. Prisoners 1, 2, 3, 4. Boxes a, b, c ,d.
1. 1 opens a+b. Chance of living = 50%.
2. 2 opens a. Sees either the name of 1, of himself, or of another prisoner. - The chance it is 1 is 50%, because he survived the first time by opening a+b. If it is 1, then 2 is in either b, c, or d. That's 33% chance of survival. Let's assume he would choose b. - The chance it is 2 is 16.67% [P(a not=1)/3 = 50/3], because then 1 would be in b and the spots a c d are divided between 2 3 4. If it is 2, then there is a 100% chance survival. - The chance it is 3 or 4 is 33.33%. This means 1 is in b, and 2 is in either c or d. That is 50% chance of survival. Let's assume he would choose c. Chance of living = .5x.33 + .1667x1 + .33x.5 = 50%.
3. 3 opens a. Sees either the name of 1, of himself, or of another prisoner. - The chance it is 1 is 50%, because he survived the first time by opening a+b. If it is 1, then 2 is in b, because he survived. That means 3 is in c or d. That's 50% chance of survival. Let's assume he would choose c. - The chance it is 2 is 16.67%. Then 3 knows he is in c or d. That's 50% chance of survival. Let's assume he would choose c. - The chance it is 3 or 4 is 33.33%. Then 3 knows he is in a or d, because 2 is in c, because he survived. If he is in a, he lives. If he is not in a, then he knows he is in d and lives. That is 100% chance of survival. Chance of living = .5x.5 + .1667x.5 + .33x1 = 66.67%.
4.4 opens a. Sees either the name of 1, of himself, or of another prisoner. - The chance it is 1 is 50%, because he survived the first time by opening a+b. If it is 1, then 2 is in b, and 3 is in c, because they survived. That means 4 is in d. That's 100% chance of survival. - The chance it is 2 is 16.67%. Then 3 is in c. Then 4 is in d. 100% chance of survival. - The chance it is 3 or 4 is 33.33%. This means 1 is in b, and 2 is in c, and 3 is in d. That is 100% chance of survival. Chance of living = 100%
Total chance = .5 x .5 x .66 x 1
Something like that. I think the method, whatever it is, should have inductive reasoning in it.
EDIT: My idea was ok, but it gets raped by that. I lose. I should post my problem later.
|
Wow Cascade congratulations you got it. Very impressive.
Here's a link from wikipedia for the calculations [link]
For those with clarification questions, you can think of the problem this way:
After the prisoners have discussed their strategy, they are taken to their own individual jail cells, far away from the other prisoners. Each prisoner goes into the room one at a time, looks at the boxes, and leaves without changing anything. Because they're in separate cells far away from eachother, they don't know who has gone when, and they cannot in anyway communicate with each other because they are isolated.
Also, all prisoners die simultaneously if any of the prisoners failed to find their name.
|
Sorry but the solutions presented in the spoilers make no sense to me. + Show Spoiler + First of all i dont understand how they get the 30% probability. Second isn't there a high probability that a box has the name written on it in it? What is the prisoner supposed to do then?
|
On January 31 2008 07:02 trickser wrote:Sorry but the solutions presented in the spoilers make no sense to me. + Show Spoiler + First of all i dont understand how they get the 30% probability. Second isn't there a high probability that a box has the name written on it in it? What is the prisoner supposed to do then?
+ Show Spoiler +the probability of it having the name in it is 1%. If he finds it on the first try, that's just good =)
|
On January 31 2008 07:49 Aepplet wrote:Show nested quote +On January 31 2008 07:02 trickser wrote:Sorry but the solutions presented in the spoilers make no sense to me. + Show Spoiler + First of all i dont understand how they get the 30% probability. Second isn't there a high probability that a box has the name written on it in it? What is the prisoner supposed to do then?
+ Show Spoiler +the probability of it having the name in it is 1%. If he finds it on the first try, that's just good =)
+ Show Spoiler +And he wont find it on the second try or later, because to get there he would have to pick the name which is in the box he should go to. If name number 5 is in box number 5, then he cant get to box number 5 by picking name 5 from another box.
The 30% isnt obvious at all. :/ If you understand the picture with the loops it will seem a bit more reasonable that it is in the range 10%-50% instead of 10^-9 though.
|
ah that's cool, I hope those prisoners got a good memory to memorize which of the 100 boxes belongs to each guy though.
|
On January 31 2008 08:20 Jonoman92 wrote: ah that's cool, I hope those prisoners got a good memory to memorize which of the 100 boxes belongs to each guy though.
Don't worry, the prisoners in these problems are typically very intelligent. In fact, I'm pretty sure they're in prison for being too smart for their own good.
|
So, I'm pretty stupid as I'm definitely wrong, but I'm just going to make things easier on the prisoners and the answer still comes out less than 25% for me.
+ Show Spoiler +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. Actually, we're going to designate two prisoners. If they both find their name, then everybody lives. Otherwise, everybody dies; if there were a 30% chance of everybody finding in any one situation each of those 30%s would satisfy these requirements too, so the chance of living is greater than or equal to 30%. We might as well remove all the boxes with the names of other prisoners, and all the other prisoners don't need to open any boxes since it has no effect in this scenario as opening a name of another prisoner has no effect and with zero information transfer somebody whose choices do not directly affect the chance of instadeath has no effect on whether the two designated prisoners find their name. As the boxes are effectively indistinguishable from the start, there is only one variable involved, how many chosen boxes overlap for designated prisoner A and designated prisoner B. We may as well rearrange the boxes in our minds so that there are first X blocks that A chooses only, 50-X that A and B choose, X that B chooses only, and 50-X that neither choose. This number X is a constant for any given runthrough. Now, lets examine where A's name is - there is a 50% chance of it lying in the first 50, and in fact, a X% chance of lying in a box B is not choosing and a 50-X% of lying in a box A and B are choosing. Examine, now, where B's name is - in the X% chance case that A's name is not in the fifty boxes that B is choosing, there are 50 boxes that say life with 99 to choose from - a (X/100)(50/99) chance that A's name is in a box he chooses but not in a box that B has chosen and that B's name is in a box that B has chosen. Consider the other case that spells life - that A's name is in the 50-X that B has also chosen. Then there are 49 unoccupied boxes that spell life for B, and 99 that spell death, giving us a ((50-X)/100)(49/99) chance that A's name is in a box that both A and B have chosen and that B's name is in a box he has chosen. This covers all cases where the names of A and B are in the fifty they have chosen, giving us a total of (X/100)(50/99) + ((50-X)/100)(49/99) chance that they have survived, or (50X + (50*49 - 49X)/(99*100) = (X + 49*50)/(99*100). But since X must be between zero and fifty, (X + 49*50)/(99*100) <= (50 + 49*50)/(99*100) = 50/198 ~= 25.2525% < 30%.
I know I must have made a small assumption somewhere in there but I can't seem to find it at all, probably in all my indistinguishability and throwing-stuff-away arguments.
|
hahaha nerdy thread. I wish i had a clue how to solve something like this. Even though im studing some ingenieering, im clueless in this problems. GJ for those who've solved it already
|
100%, the prisoners all have the same name.
|
Oh shit I missed this, it sounds like fun!
Guess nobody will read this now but I'm gonna try to solve and post it now anyway -_-
|
Ok here we go! Well the only thing they could really do to go beyond a probability of ~1/2^100 is to associate a boxes with their names. When a prisoner enters he goes to his own named box, opens, goes to the name he finds there....and so on.
This will mean they all survives if the permutation of names in boxes contains no orbits of greater length than 50.
Now for the calculation of the probability
The probability that there IS atleast 1 orbit with greater length than 50 will be exactly: p=(Sum n=51..100((100 over n)(n-1)!(100-n)!))/100!
+ Show Spoiler [explanation] + For each term of the sum:
(100 over n) (means the binomial coefficient): Pick n of the boxes.
(n-1)!: put theese n boxes in an orbit. Start with the n'th box where you have n-1 possibilites for a name to another box: everone except itself. For the n-1'th box you can pick any box except itself and the n'th box and so on.
(100-n)!: Permute the remaining 100-n boxes arbitrarily (doesn't matter how many orbits arises here)
The sum will then contain all cases where the longest orbit is 51 or longer. Then divide by all possible permutations=100! to get the probability p.
Expand the binomial coefficient and do some basic arithmetic and it amazingly reduces to almost nothing:
p=Sum n=51..100 (1/n)
Now for a value, compare it with an integral
p < Integral x=50..100 (dx/x) = ln 100-ln 50=ln 100/50 = ln 2
So the chance that they survive=1-p is greater than 1-ln2 ~=0.31
Another quick integral comparison shows that the error in this number will be about 0.005.
A fun thing is that it doesn't matter how many prisoners there are, as long as they can pick half of the boxes. With a million prisoners you get even closer to 1-ln2.
Nice problem, keep posting these!
|
|
|
|