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