5 ms·

I always liked the prisoner box question, but I prefer the phrasing where the prisoners are assigned a number and the boxes are numbered. I feel like the "priso

I always liked the prisoner box question, but I prefer the phrasing where the prisoners are assigned a number and the boxes are numbered. I feel like the "prisoners have to come up with a name to number mapping" step just gets in the way of the interesting part.

ColinWright 8y ago
If the evil dictator does the naming/numbering then they can guarantee failure. The randomisation of the numbering of the prisoners is important to avoid that.
CamperBob2 8y ago
I don't understand one assertion that the author makes in the solution, though: If it happens that the permutation has no cycles of length greater than 50, this process will work every time and the prisoners will be spared. Obviously that's not true as written, because the first prisoner has odds of 50% no matter what function or algorithm they use to choose the boxes they open. If they fail in their initial guesses, the game stops immediately and everyone dies. What am I missing? Furthermore, if you simplify the case to two prisoners and two boxes, where each is allowed to open one box, the odds of "success" are clearly only 25%. What happens as the number of prisoners and boxes grows that improves the odds? This isn't a classic Monty Hall variation where the participants have additional options as the game progresses -- it's completely predetermined.
- fydorm 8y ago
  If it has cycles of 50 or less only, then they're guaranteed to find their own name (they start the cycle on the box corresponding to themselves, so that cycle must contain them). Incidentally, the "first prisoner" might as well be every prisoner, because they aren't allowed to observe each other, communicate, or modify the room.
  - CamperBob2 8y ago
    If it has cycles of 50 or less only, then they're guaranteed to find their own name (they start the cycle on the box corresponding to themselves, so that cycle must contain them) But there are 100 boxes, assigned at random. The prisoners can come up with a mapping function that predetermines which boxes they will open based on their names, but that function will have no relationship to the one (if any) that was used by the warden. There is no way to guarantee that the first prisoner finds his name, and that seems to be true for all of the others. It must genuinely be a case where I haven't understood the problem correctly.
    - function_seven 8y ago
      If no cycle is longer than 50 boxes (~30% chance of that being true), then by starting with the box that matches your number, you have a 100% chance of navigating to the box containing your number before your 50-box limit is reached. It’s impossible to start in the wrong cycle, because that cycle contains neither the pointer or the value. You have to find your pointer in a circular linked list. But it’s only singly-linked, so you start just in front of it and work around the links the long way. 30% of the time, all the lists are 50 elements or shorter, meaning everyone is guaranteed to succeed.
      - CamperBob2 8y ago
        But what if your name is in box #51, which you aren't allowed to open?
        bewaretheirs 8y ago
        Then there's a cycle of length > 50 and everyone loses.
        function_seven 8y ago
        Like sibling says, this only happens when there’s a cycle longer than 50. In that case, you’re all doomed.
- bsdetector 8y ago
  > Furthermore, if you simplify the case to two prisoners and two boxes, where each is allowed to open one box, the odds of "success" are clearly only 25%. No it's still 50%, because first person opens box 1 and second person opens box 2. They both either live or die together. Three people, 2 chances. Each just guessing independently would be 2/3 chance so the chance for all to win is (2/3)^3 or 30%. But if the first person opens box 1 then they will find their name or not (1/3) and if so the second and third opening 2 and 3 are guaranteed to find their name, so 33% total chance. The basic idea is that you choose boxes in a dependent pattern so that group either all wins or all loses as much as possible. The more people that can win or lose at the same time the better the overall chance for the group.
  - CamperBob2 8y ago
    No it's still 50%, because first person opens box 1 and second person opens box 2. They both either live or die together. As the problem is stated, the boxes remain where they are and must be reclosed after being opened. There are no other choices to be made, there's no way to retain or communicate any information about a particular prisoner's actions, and there are no order-dependent aspects to the problem. Everybody sees the same 100 closed boxes and gets to open 50 of them.
    - bsdetector 8y ago
      > there's no way to retain or communicate any information about a particular prisoner's actions The communication happens before the people go in to open the boxes. In the 2-person 2-box 1-choice example, person 1 says to person 2 "I'll open box 1 and you open box 2". With person 1 always opening box 1 and person 2 always opening box 2, what do you feel their chances are? List out the permutations and see.
      - CamperBob2 8y ago
        I'll grant that with two people, they have a 50% chance of survival, because there's no way that only one of them can be right. But with more than two, the odds seem to get worse in a hurry. Presumably the same exclusion principle that improves their odds from the "obvious" 25% to 50% will apply to any larger number of participants, and converge near 30%... but it's certainly unintuitive.

ColinWright 8y ago

If the evil dictator does the naming/numbering then they can guarantee failure. The randomisation of the numbering of the prisoners is important to avoid that.

CamperBob2 8y ago

I don't understand one assertion that the author makes in the solution, though: If it happens that the permutation has no cycles of length greater than 50, this process will work every time and the prisoners will be spared. Obviously that's not true as written, because the first prisoner has odds of 50% no matter what function or algorithm they use to choose the boxes they open. If they fail in their initial guesses, the game stops immediately and everyone dies. What am I missing? Furthermore, if you simplify the case to two prisoners and two boxes, where each is allowed to open one box, the odds of "success" are clearly only 25%. What happens as the number of prisoners and boxes grows that improves the odds? This isn't a classic Monty Hall variation where the participants have additional options as the game progresses -- it's completely predetermined.

fydorm 8y ago
If it has cycles of 50 or less only, then they're guaranteed to find their own name (they start the cycle on the box corresponding to themselves, so that cycle must contain them). Incidentally, the "first prisoner" might as well be every prisoner, because they aren't allowed to observe each other, communicate, or modify the room.
- CamperBob2 8y ago
  If it has cycles of 50 or less only, then they're guaranteed to find their own name (they start the cycle on the box corresponding to themselves, so that cycle must contain them) But there are 100 boxes, assigned at random. The prisoners can come up with a mapping function that predetermines which boxes they will open based on their names, but that function will have no relationship to the one (if any) that was used by the warden. There is no way to guarantee that the first prisoner finds his name, and that seems to be true for all of the others. It must genuinely be a case where I haven't understood the problem correctly.
  - function_seven 8y ago
    If no cycle is longer than 50 boxes (~30% chance of that being true), then by starting with the box that matches your number, you have a 100% chance of navigating to the box containing your number before your 50-box limit is reached. It’s impossible to start in the wrong cycle, because that cycle contains neither the pointer or the value. You have to find your pointer in a circular linked list. But it’s only singly-linked, so you start just in front of it and work around the links the long way. 30% of the time, all the lists are 50 elements or shorter, meaning everyone is guaranteed to succeed.
    - CamperBob2 8y ago
      But what if your name is in box #51, which you aren't allowed to open?
      - bewaretheirs 8y ago
        Then there's a cycle of length > 50 and everyone loses.
      - function_seven 8y ago
        Like sibling says, this only happens when there’s a cycle longer than 50. In that case, you’re all doomed.
bsdetector 8y ago
> Furthermore, if you simplify the case to two prisoners and two boxes, where each is allowed to open one box, the odds of "success" are clearly only 25%. No it's still 50%, because first person opens box 1 and second person opens box 2. They both either live or die together. Three people, 2 chances. Each just guessing independently would be 2/3 chance so the chance for all to win is (2/3)^3 or 30%. But if the first person opens box 1 then they will find their name or not (1/3) and if so the second and third opening 2 and 3 are guaranteed to find their name, so 33% total chance. The basic idea is that you choose boxes in a dependent pattern so that group either all wins or all loses as much as possible. The more people that can win or lose at the same time the better the overall chance for the group.
- CamperBob2 8y ago
  No it's still 50%, because first person opens box 1 and second person opens box 2. They both either live or die together. As the problem is stated, the boxes remain where they are and must be reclosed after being opened. There are no other choices to be made, there's no way to retain or communicate any information about a particular prisoner's actions, and there are no order-dependent aspects to the problem. Everybody sees the same 100 closed boxes and gets to open 50 of them.
  - bsdetector 8y ago
    > there's no way to retain or communicate any information about a particular prisoner's actions The communication happens before the people go in to open the boxes. In the 2-person 2-box 1-choice example, person 1 says to person 2 "I'll open box 1 and you open box 2". With person 1 always opening box 1 and person 2 always opening box 2, what do you feel their chances are? List out the permutations and see.
    - CamperBob2 8y ago
      I'll grant that with two people, they have a 50% chance of survival, because there's no way that only one of them can be right. But with more than two, the odds seem to get worse in a hurry. Presumably the same exclusion principle that improves their odds from the "obvious" 25% to 50% will apply to any larger number of participants, and converge near 30%... but it's certainly unintuitive.