[CamperBob2]

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]

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]

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]

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]

But what if your name is in box #51, which you aren't allowed to open?

[bewaretheirs]

Then there's a cycle of length > 50 and everyone loses.

[function_seven]

Like sibling says, this only happens when there’s a cycle longer than 50. In that case, you’re all doomed.

[bsdetector]

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

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]

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

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.

[bsdetector]

Yeah the solution doesn't even try to explain it intuitively.

Worse, they actively confuse the issue by making the warden an adversary and adding another layer of randomness that's just a red herring. Instead imagine they just put their names in alphabetical order so box 1 is Andy, box 2 is Bob, and so on.

First consider if they were randomly ordered buttons and everyone had to press their button. The people can plan out any order of pressing buttons, it doesn't matter because each person has to win their own separate 50 in 100 bet. So this should be intuitive. (1/2)^100 is impossible odds.

The key part is this: "He then looks into the box belonging to the name he just found".

They are picking an order that's based on the arrangement of names in boxes so they are no longer acting independently from the random box-name arrangement. If everybody was assigned some arbitrary starting box, they are not making 100 separate choices anymore they are making 1 collective choice. But it's the same chance! Instead of making 100 separate fairly likely choices, they are making 1 very unlikely choice (that the starting box order they picked is right).

The second key is starting with the box assigned to their own name.

So imagine this problem as a directed graph. Each person's box is a node and the name within is a directed edge to another node. Every node has exactly one edge to it and one edge from it, and the edges are all random. It's incredibly unlikely to be one full circuit though, instead there are little isolated circuits. For example, box 1 could have "Bob" and box 2 could have "Andy" and if anybody else picked box 1 as their starting box they would never find their name, instead finding 25 Bobs and 25 Andys.

By picking their own box, they're guaranteed to be on a circuit that has their name on it and they are excluding all other random arrangements, so Conan getting stuck on an Alex-Bob circuit of 2 is impossible. The only question is if it will take more than 50 steps.

Now imagine you are randomly constructing this directed graph one step at a time. You open box 1 (Andy's box) and randomly put in Conan, open box 3 (Conan's box) and put in Xavier - can't be Conan because you already used that name! Every next step in a chain has an increasing chance of coming back to the beginning. So on the second step there's 99 names left and one of them is Andy, on the third step there's 98 left and one is Andy. The longer the chain, the more likely it is to end and become a circuit. The warden won't be following this process to assign names, but since every step is random it's the same result as any other random way to assign names to boxes.

So the longer the chain the more likely to become a circuit, and the shorter every other circuit has to be, is finally the reason why the win chance is higher than seems possible.

Why it's 30.5% instead of 23% or something else. Well, imagine the first chain being constructed. The chance of it getting longer than 50 is (99/100)(98/99)...(50/51) which works out to 50%. So the first person (Andy) opening his box has a 50% chance that his chain got longer than 50 before it become a circuit - exactly what you'd expect for the first box. But the chance of building the second chain longer than 50 is much smaller because the first one took a lot of names out of the hat, so say first circuit is 25 long, second chain is (74/75)(73/74)... so you'll have to ask a math genius how to estimate that, but intuitively it's much less likely.