4 ms·
I think you messed up the formulation of the problem. As stated, a strategy would be - first prisoner opens 50 boxes. - second prisoner opens the other 50. - ea
by Someone 16y ago
I think you messed up the formulation of the problem. As stated, a strategy would be
- first prisoner opens 50 boxes.
- second prisoner opens the other 50.
- each prisoner finds the box with the paper with his
name on it.
Success rate: 100%. There probably are other constraints but I can only guess at them (do they visit the room one by one, and must they decide on a box to choose before leaving? Who can talk to whom? Must they close all boxes before leaving the room?)
- jonafato 16y agoI think the problem statement means that each prisoner must find his name independently of one another. e.g. Prisoner 1 opens 50 boxes, finds his name, then the boxes are closed and Prisoner 2 must do the same without any help.
- RiderOfGiraffes 16y agoI believe the statement as made is correct, although not necessarily as clear as it could be. For example, your suggested "strategy" is wrong - the first prisoner as you've stated only has a 50% chance. Further, after each prisoner the boxes are closed so that each prisoner finds the room is exactly the same state, with no communication between them.
- Someone 16y agoApparently, my formulation isn't as clear as it could be, either :-) My 'solution' has all of the prisoners point out 'their' box after the second one has opened the last 50 boxes. As to the 'no communication between': if there is no communication, it seems each of them cannot do better than 51/100 (50 opened boxes, and if their name isn't there, a 2% gamble) However that isn't true. Suppose the first 51 each open the first 50 boxes and decide to choose the 51st box if they do not find their name, Then, all others, working under the assumption that the first 51 found their name (if they didn't, the game is lost anyways), can just open the last 49 and be certain to find their name. That would bring the probability to about 2^-50. I doubt that is the optimal strategy, though. There seems to be much more room between 1/100! and 0.01^100.
- RiderOfGiraffes 16y agoI still, really don't understand what you're suggesting. Let's go carefully. The first person opens 50 boxes. Let's suppose they find their own name (otherwise we're dead anyway). They leave the room, everything is put back exactly as it was, they're not allowed to communicate with the others. It seems to me you're suggesting the next person opens the second batch of 50. OK. But then they leave the room, everything is put back exactly as it was, and they're not allowed to communicate with the others. What does the third person do? They're confronted by 100 closed boxes with no idea of anything, except that the first person's name is in the first 50 boxes, and the second person's name is in the second 50 boxes. So, what now?
- dedward 16y agoHow do they even know that? Does the game continue until the end - or does it end as soon as one person fails to find their name?
- RiderOfGiraffes 16y agoThey don't know that, but you may as well assume they do, because otherwise anything they do is pointless and has no effect.
- dedward 16y agoTrue - but you only know that at the end of the puzzle. The point of the exercise is to maximize their strategy of winning. There is no "winning" strategy - but there is one that is significantly better than what immediately comes to mind.
- RiderOfGiraffes 16y agoBut that's not the point. The point is that without loss of generality each person can assume that the people before have all found their own names. If not then it makes no difference what they do, they're all doomed. Unless I've misunderstood you.
- photon_off 16y agoI see what you mean. Prisoner 1 could memorize all of the names and just tell the next one if he's in the front or back 50. The catch is: once the prisoners decide on a strategy, they are not permitted to communicate anymore.