100 Prisoner Riddle

[Hadoblado]

This is difficult, people might not solve it (I didn't). Please spoiler your answers if you're sure you have the solution or if you've encountered this riddle before. Please don't cheat. I will provide the answer once everyone who participates has given it a fair go.

100 prisoners are on death row. They are offered the chance to live if they successfully complete a game of chance.

The rules are as follows:

• Each prisoner has a number from 1 to 100.

Spoiler

• Each prisoner enters the box room, containing 100 boxes, each box has a number on top from 1 to 100 in order.

Spoiler

• In each of the boxes, a piece of paper with a number from 1 to 100 is placed. For example:

Spoiler

• Each prisoner must find their number before leaving the room or all prisoners die. Prisoners do not keep their number, they place it back in the box they found it in.
• Each prisoner can open up to 50 boxes before they must leave the room.
  • If a prisoner opens their 50th box without finding their number, all prisoners are executed immediately.
• The room is hard reset after each prisoner down to the atom.
  • There is zero communication between prisoners who have entered the room, and those who haven't. No exceptions, this is not a trick question. For all intents and purposes the only thing the prisoners will know about each other following the experience is that they did not get executed.

The prisoners are free to come up with a strategy beforehand. All communication occurs before entering the room.

What should the prisoners plan in order to secure the greatest chance of success?

There is no fool-proof answer. The best-known solution has a <33% success rate. If each prisoner guesses at random, their chances are basically zero. This question is honest and the answer is maths based but unintuitive. If you have a question I'll answer it, but chances are if you're unsure if it's allowed it's not allowed.

 

[Daddy]

This seems a lot like the traveling salesman problem.

edit: I guess if you knew what box would lead to a chain of boxes that would lead to your number, you could start with that. But you don't.

 

[onesteptwostep]

I have some questions, are the numbers in the box the same in each of the rooms? Like is the number X always in box Y in all the 100 rooms or is that also random as well. Or is it just that there is a single room that has the 100 boxes? How many rooms are there in this scenario?

 

[Hadoblado]

For all intents and purposes there are three "rooms". Room one where prisoners can discuss before entering the room with the boxes. Room two has the 100 boxes and is "reset" for each prisoner. Room three is the space that the prisoners leave to afterward (room three exists only to prevent communication and does not factor into the riddle at all).

The numbers remain in the same box after reset. So if the first person looks in box 1 and finds a specific number, the second person will find the same number if they look in box 1.

The riddle could be reframed so that the second room is actually 100 identical rooms which the prisoners enter simultaneously (it doesn't matter, so long as prisoners can't inform each other).

 

[Puffy]

I know the 30% solution to this one as I’ve come across it before but I won’t pretend I can understand the math. It was 100 drawers containing 100 notes iirc in the version I saw but it’s the same math problem.

 

[Daddy]

Ohh, I thought it was different for each prisoner. Now that’s interesting. I'm going to give this a try then. Had no idea, if they were all different and random.

 

[Daddy]

So far this is what I have

Spoiler

If we choose some boxes and see that

1. More Even number boxes are left to choose from
a. More even numbers left -> we assume even boxes chooses even numbers and odd boxes chooses odd numbers
b. More odd numbers left -> we assume that even boxes choose odd numbers and odd boxes choose even numbers
2. More Odd number boxes left
a. More even numbers left -> we assume odd chooses even and even chooses odd
b. More odd numbers left -> we assume odd chooses odd and even chooses even

Not sure if this is the right idea, but it's all I got, since the prisoners can't inform one another. I'm not even sure this helps. Okay, this riddle is hard.

 

[dr froyd]

@Hadoblado by "theres no fool-proof answer" do you mean the optimal solution is not known? or just that several answers can lead to a better probability than 0.5^100 but not necessarily optimal

 

[Puffy]

@Hadoblado by "theres no fool-proof answer" do you mean the optimal solution is not known? or just that several answers can lead to a better probability than 0.5^100 but not necessarily optimal

I think he means that the 33% probability solution is the most optimal solution that’s been offered so far.

 

[Hadoblado]

@dr froyd
I mean that there isn't a solution where survival is guaranteed. It's about making the best of a bad situation. Most riddles have an answer that is more of a happy ending.

@Daddy
Not sure if I'm interpreting you correctly, but there is no evidence of "boxes left". Each prisoner that finds their number must leave it there - sorry if that makes it less interesting. Yep it's hard. I gave up after about 15 minutes of smacking my head against it.

 

[Daddy]

I understand. I was trying to figure out a way that a prisoner could weigh what they have currently learned with what was opened against what hasn't been opened, since that's all they can do.

But I gave up and looked up the 33% answer and would like to discuss the justification at some point. Please let me know if it ever gets to that.

 

[Hadoblado]

I might give it one more day if there's no more interest.

 

[dr froyd]

haven't verified this but its a sketch for an idea that kinda works i think

Spoiler

say that every guy always jumps the number of boxes that he finds in each box (in particular if the number in box k is j, he jumps to (k + j) mod 100).

so if guy 1 opens 37, he jumps 37 places. If that box happens to contain 1, he stops. So later, if 37 encounters 1, he knows that 37 is exactly 37 places before that.

that way, if the prisoners go in sorted, 1, 2, 3.. then any prisoner p, whenever he encounters a number j < p he knows the exact position of his box by subtracting p from the current position. They should probably do it so that 1 starts at box 1, 2 starts at 2 etc.

getting a bit late for math now but this probability roughly corresponds to 0.5 * 0.75 * ... * (1 - 0.5^100) which is close to 30%

regardless of whether its correct or not - very cool and difficult problem

 

[Hadoblado]

Re: Froyd

Spoiler

So prisoner #1 starts and selects box #1 first. From here, they have a 50/50 chance of finding paper #1 in 50 tries.

Prisoner #2 comes in. He finds paper #1 in box #37. Does Prisoner #2 assume that prisoner #1 jumped two spaces from #35?

What happens when Prisoner #3 opens box #37 and finds paper #1, do they assume that Prisoner #1 jumped three from box #34?

How does each prisoner know that previous prisoners used their number?

Good pieces to a solution, but I'm not sure this works as written? Yeah I like this problem - I don't know much about maths and I feel like I learned something from this.

 

[onesteptwostep]

I saw the veritasium video

I didn't watch the part where they explain the math yet, but I'm curious and intrigued at how they came up with the 31%

 

[Hadoblado]

I couldn't reproduce the math off the top of my head, for me it's more about the divergent process of generating approaches whether they're successful or not. I suspect that when I do reveal, if nobody has the answer yet there will be people here who can produce the math once they've got the right direction.

 

[dr froyd]

Re: Froyd

Spoiler

So prisoner #1 starts and selects box #1 first. From here, they have a 50/50 chance of finding paper #1 in 50 tries.

Prisoner #2 comes in. He finds paper #1 in box #37. Does Prisoner #2 assume that prisoner #1 jumped two spaces from #35?

What happens when Prisoner #3 opens box #37 and finds paper #1, do they assume that Prisoner #1 jumped three from box #34?

How does each prisoner know that previous prisoners used their number?

Good pieces to a solution, but I'm not sure this works as written? Yeah I like this problem - I don't know much about maths and I feel like I learned something from this.

Spoiler

yeah it doesn't work.

maybe instead of jumping the number inside the box, they need to jump by some function of both the box number and the number inside. This cannot map uniquely to a new box so the next guy somehow needs to invert the jump function and look through multiple solutions to find his number.

that sounds like hash-function theory stuff, this is getting heavy, or im on the completely wrong track

will be very interesting to see the solution

edit: i saw the veritasium video now lol. Very cool. .

 

[Hadoblado]

Heh I was trying to keep it secret until the reveal. You were doing well and in a way kind of overthought it but I didn't want to say too much in fear of ruining it.

 

[Ex-User (9086)]

I knew the solution. To me it looks like a data structure problem with a singly linked list. Each box has a known address and holds the value of the next address, the pointer to another box, but the pointers were randomly scrambled.

This wasn't illustrated well in the veritasium video. One important thing to note is that players MUST check their numbered box first. If they don't, then they risk entering a linked list of numbers that doesn't include their own.

You can look at a 6 element list to illustrate why everyone must check their number. For 6 boxes the player only gets 3 guesses. We want to find number 1.
Suppose we have elements (boxes) 1, 2, 3, 4, 5, 6. And they hold numbers inside like so 1(1) is a box numbered 1 with a number (1) inside.

So a randomly arranged list could be like this 1(1), 2(5), 3(4), 4(3), 5(6), 6(2). You can see that there are 3 separate "graphs" or list structures.
1->1
2->5->6->2
3->4->3
If the player decides to start with any other number but their own, they will never enter a chain leading to their number. They're going to be stuck in a "train" loop that goes through the wrong stations.

Let's look at a different list 1(2), 2(3), 3(1), 4(5), 5(6), 6(4).
2 lists:
1->2->3->1
4->5->6->4
Looking at it we can say that:
1. There can never be a broken list, a list that doesn't return back to its starting element.
2. All boxes of a given number belong to a list of one or more boxes that store all of their numbers and loop back.
3. The number we're looking for is either in the box with the same number OR it MUST be in the list chain that includes the box of that number. There can't be a situation where it doesn't hold like 2(1), 1(3), 3(4), 4(5), 5(6), 6(3) because now box 6 needs to point to something other than 2, and this violates the rules (rules being that each box holds a different number, numbers don't repeat, each box has to hold a number). Even if box 1 doesn't store its own number, it must belong to a list that points to number 1 because there needs to be an element z->1 that points to it. That element is pointed to by x->z->1 and 1 necessarily points to something that leads to x->z->1.


New more difficult game. 100 numbered boxes, 100 numbered prisoners BUT crucially each box can hold between 0 and 100 numbers and numbers don't repeat. So going back to the 6 box example we can get a list like this:
Box 1 - 0 numbers inside
Boxes 2 through 4 - 0 numbers inside
Box 5 - number 2 inside
Box 6 - numbers 1, 3, 4, 5 and 6 inside.

What's the optimal strategy for this variant?

 

[Hadoblado]

Bunch of cheaters I swear... Okay it's done. The strategy is as Glaer says:

• Each prisoner checks the box with their number on it first.
• The prisoner then checks the box with the number of the paper they find inside.
• Repeat until you find your number.
• That's it.

Spoiler

By adopting this strategy, you are betting that collectively there is not a loop larger than half the size of the pool. So this strategy does not work if there is a loop of 51 or larger, but the chances of that occurring are... around 69%, leaving you with 31% survival: Better than a group of two choosing at random.

I was hoping to discuss it more but I guess people grew impatient with it. Froyd was damn close, just over-complicated the mechanism of determining the next box.

 

[Puffy]

@Glaerhaidh I didn’t understand the solution before but that’s well explained, thanks!

@Hadoblado Glaer has given a harder version of the puzzle in his post you could discuss between you. I cba to not cheat on this type of thing so I’ll just cheer you on in the side-lines as I clean my flat.

 

[Hadoblado]

How is the distribution of paper to boxes determined? I assume for each paper a d100 is rolled?

I can't think of anything that improves chances much. I still think you start at the box with your own number to remove the possibility of prisoners looking in the same place for different numbers. Loops are still possible but so are strings or even complete whiffs.

I can't figure out how to guarantee how to put your search on the same track as your number like in the last problem

 

[Cognisant]

Redefine success, if a suicidal prisoner refuses to participate their success is guaranteed and everybody dies.

 

[Ex-User (9086)]

How is the distribution of paper to boxes determined? I assume for each paper a d100 is rolled?

I can't think of anything that improves chances much. I still think you start at the box with your own number to remove the possibility of prisoners looking in the same place for different numbers. Loops are still possible but so are strings or even complete whiffs.

I can't figure out how to guarantee how to put your search on the same track as your number like in the last problem

We have 100 boxes and 100 numbered cards between 1 and 100.
1. Choose the starting box at random, so choose between 1 and 100 or roll d100. Suppose your random number was 42.
2. Go to 42 and choose a number between 0 and 100 (roll d101). If you rolled 0 then you put 0 numbered cards in the box. Suppose that you rolled 11, put 11 randomly selected numbered cards between 1 and 100 in the box numbered 42. You have 89 unique addresses (numbers) left.
3. Choose a number between 1 and 99 at random (roll d99). This time don't go to the number you got, but add the random number to the number of the box you're standing next to. If the number exceeds 100 then subtract 100. So if you got a random number 85, just add it to 42 and you get 127, subtract 100 and you need to go to box 27.
4. At box 27 choose a random number between 0 and 89, which is how many numbered cards there are remaining.
5. Repeat until you run out of numbered cards to distribute.

I think in the modified game, the average number of boxes with ANY addresses will be 4. The remaining 96 boxes will be empty.

Spoiler: strategy

Here I think there's a strategy that's better than everyone choosing 50 boxes at random. Prisoners should agree on the same sequence of boxes to check and hope that all addresses that they need are in that half of boxes. The probability that the average 4 non-empty boxes are in the 50 selected boxes is higher than the probability of each 100 prisoners finding something by choosing their own 50.

 

[Daddy]

I don't understand.
Let's say our number is one and we open box 1 and it reveals the number 3, as follows
1(3) -> 3(16) -> 16(3)

3 and 16 can loop back, without revealing one. There's no guarantee your box's starting loop has to lead back to itself. The assumption only works, if no other boxes in the loop lead back to each other first.

Or am I misunderstanding something? This is why I said this earlier

"I guess if you knew what box would lead to a chain of boxes that would lead to your number, you could start with that. But you don't."

Also, assuming I'm wrong about that or that it isn't a problem, what's the probability that you get a chain > 50? Cause in order to get 31% chance of success, then the chances of one chain < 50 can't be 69%, it has to be

1 / (x^100) = 31/100 gives 3.226 = x^100 gives x = 1.01177, so 1 / 1.0117 chance of succes, or a 98.8% chance of success for each prisoner that for all of them to succeed is 31%. yes?

I'm frustrated and confused at the supposed 31% answer, lol. I never liked statistics.


edit: sorry, had a lot of grammatical errors.

 

[Ex-User (9086)]

@Hadoblado In case you're interested I ran a test for 1 million games:
1. the average amount of non-empty boxes is 5.06118.
2. success rate with my strategy is 5.6553 % compared to 7.8886090522101180541172856528278622967320643510902300477027×10^-29% for no strategy (That's 0.0...78 percent with 29 zeroes - super unlikely)
3. In a sample of 1 mil the largest amount of non-empty boxes was 16, lowest 1 ofc (I was expecting greater amounts of non-empty boxes at least sometimes, theoretical max is 100 so it's interesting that going beyond 20 is very unlikely)

I don't understand.
Let's say our number is one and we open box 1 and it reveals the number 3, as follows
1(3) -> 3(16) -> 16(3)

Can't have two boxes addressed to 3, the addresses are non-repeating because they're supposed to represent prisoner ID's that are unique. We don't have 2 prisoners with the same ID or similarly we don't have a situation with two cards numbered "3" as that means one prisoner doesn't have their own card and can never finish the game. So 16 is forced to point to something that wasn't used previously and this forces the loop to close.

There are 3 elements in this game. 100 prisoners, each with a unique number 1 through 100. Prisoner ID's or "numbered cards" each unique 1 through 100. Boxes, each unique 1 through 100.

 

[dr froyd]

@Glaerhaidh you're just a madman rambling about linked lists lmao. where's the probabilistic aspect of the solution?

i mean how do you create a tought process that actually solves the problem instead of backwards-engineering a known solution

 

[Ex-User (9086)]

Lol dude, you're acting like a grumpy old fart, can you shed 30 years for like a second before you speak?

The boxes in the 100 prisoner problem are clearly a linked list and I find that property to be useful. It shows that the whole box "network" has 1 or more lists and the only list that has the searched number includes the box with the same number on it.

If you ask me it's a computer science problem and not a maths problem, but sure you can use maths if you were born before internet was a thing.

 

[Hadoblado]

Relaaaaax guys it's a riddle. One of you does maths the other does programming. I don't see the issue.

Re: New problem
Oh that's wild. Without reading your strategy, I think the best approach is to all-in on a specific number and hope for a favourable distribution. So everyone starts at 1, if no 1 => march forward in ones and hope that all the rolls were in the first half of the distribution.

This will be much weaker than the solution for the other problem. Probably 0-2% at guess.

Edit: Looks like we arrived at similar conclusions.

 

[Hadoblado]

I don't understand.
Let's say our number is one and we open box 1 and it reveals the number 3, as follows
1(3) -> 3(16) -> 16(3)

3 and 16 can loop back, without revealing one. There's no guarantee your box's starting loop has to lead back to itself. The assumption only works, if no other boxes in the loop lead back to each other first.

Or am I misunderstanding something? This is why I said this earlier

"I guess if you knew what box would lead to a chain of boxes that would lead to your number, you could start with that. But you don't."

When you open a box, there are 3 possibilities:
1) it's your number, making a loop and ending the game
2) it's a new number extending the string
3) it's a repeat of a number, making a lasso

Except (3) is impossible since there is only one of each number. If I open box 1 first, it points me to box 2, then paper #2 has already been used and is no longer in the pool. So when I open the third box, the possibility of repeating the number of a box other than the one I started on is zero. This is true for every subsequent choice.

You now have two possibilities:
1) it's your number, making a loop and ending the game
2) it's a new number extending the string

Therefore the moment you select your own number on the first box, you are guaranteed to loop back to this box eventually. Your success is determined by whether the loop is larger than the number of tries you have. The chances of this occurring are 69%, giving the 31% success rate.

 

[Hadoblado]

Also, assuming I'm wrong about that or that it isn't a problem, what's the probability that you get a chain > 50? Cause in order to get 31% chance of success, then the chances of one chain < 50 can't be 69%, it has to be

1 / (x^100) = 31/100 gives 3.226 = x^100 gives x = 1.01177, so 1 / 1.0117 chance of succes, or a 98.8% chance of success for each prisoner that for all of them to succeed is 31%. yes?

I'm frustrated and confused at the supposed 31% answer, lol. I never liked statistics.

That's cool. This is actually the sort of conversation I was wanting to have. I like statistics but not math in general, so finding ways to have conversations about niche stats is a good way for me to extend my engagement. When I read your explanation my mind fogs over. Collaboration helps everyone learn.

Reading your statement, there might be a misconception? The chance that any single prisoner succeeds is identical to the probability that all prisoners succeed so calculating them separately does not make sense. The chance of an individual prisoner succeeding is 31% in the proposed solution.

The probability of a loop <50 is arrived at by the sum of p(x=51), p(x=52)...(p(x=100). Have you tried this? p(x=100)=(100!/100)/100!

 

[Daddy]

Oh okay, lol. That makes sense. I had also forgotten that each prisoner has the same layout. I'll have to look into the math's probability aspect of that. I'm guessing your right Hado.

 

[Rook]

as a prisoner i wouldnt wanna try and figure something like this out. if there's 100 of us and theyre willing to kill all of us related to the... opening of boxes ill either be planning to escape or find someone to help me and rig the box game. hundred prisoners storming at once can at least mean mpost of us have a chance of forcing our way out, no?

 

[dr froyd]

i feel like there's been a lot of focus on the mechanism of the solution strategy but not the actual probabilistic aspect of the problem – which is the actual problem; the problem is not whether you can find a sequence that always ends up with your box or whatever. The question is how do you maximize the probability for the entire prisoner population, and why the is proposed solution strategy even a good one from that point of view.

it was briefly mentioned in the veritasium video that it relates to the probability dependence between each prisoner. But in fact that's the entire basis for the solution

to take a very simplified example, say we have just 2 prisoners, 2 boxes, and 1 try each. If they pick boxes randomly, their probability of surviving is (1/2)^2 = 1/4. But if they say that they take one specific box each (doesn't matter which), for example guy 1 takes box 2 and second guy takes box 1, their chance increases to 1/2, because there's only 2 possibilities: either the boxes contain the permutation {1, 2}, or {2, 1}. They are effectively betting on the second one, and the probability that this is the actual one is 1/2. The reason their probability increased is that they made the success of one dependent on the other - they fail and succeed in the same permutation. In particular the probability of 2 events, say A and B, happening is P(A and B) = P(A | B)P(B). In this chosen strategy, the second guy's probability of succeeding given that first guy succeeded is 1, so the combined probability is in fact just the probability of the first guy succeeding.

a slightly more complicated case shows why the true solution actually works; take 3 prisoners, 3 boxes, and 2 tries. There are 3! = 6 permutations. If they pick randomly their probability is (2/3)^3 = 8 / 27. If they do the scheme in the solution, the success table looks like this (the top line shows prisoner number, permutation is the sequence of numbers inside the boxes, and * indicates success - they need a row with all 3 succeeding in order to survive)

 permutation  | 1 | 2 | 3 |
-----------------------------
    1 2 3     | * | * | * | <
    1 3 2     | * | * | * | <
    2 1 3     | * | * | * | <
    2 3 1     |   |   |
    3 1 2     |   |   |
    3 2 1     | * | * | * | <

so as one can see they all succeed in the exact same permutations, which happens in 4 / 6 of them.

if they engage in any other strategy, say, guy 1 takes boxes {1, 2}, guy 2 takes {2, 3}, and guy 3 takes {1, 3} then the table looks like this

permutation  | 1 | 2 | 3 |
-----------------------------
    1 2 3    | * | * | * |   <
    1 3 2    | * | * |   |
    2 1 3    | * |   | * |
    2 3 1    |   |   |   |
    3 1 2    | * | * | * |  <
    3 2 1    |   | * | * |

where only 2 permutations result in all three succeeding, and a probability of 2 / 6. That's an improvement over the random-choice strategy giving 8 / 27 but still far from optimal. That's because there's now more independence in their individual probabilities.

the thought process of how one would actually arrive at the optimal solution is very difficult to find though, I don't have any good suggestions for that. I would love to hear it if anyone has.

 

[Daddy]

So I was thinking about this now that it's the weekend and I can be lazy,

2 boxes -> 2 x 1 = 2 or 2! combinations
3 boxes -> 3 x 2 = 6 or 3! combinations
4 boxes -> 4 x 6 = 4 x 3x2x1 = 24 or 4! combinations
5 boxes -> 5 x 24 = 5 x 4x3x2x1 = 120 or 5! combinations

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2

2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1

3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1

4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

example, say your number is 2 then
Open box 2 to start

1 2 3 4 win
1 2 4 3 win
1 3 2 4 win
1 3 4 2 lose
1 4 2 3 lose
1 4 3 2 win

2 1 3 4 win
2 1 4 3 win
2 3 1 4 lose
2 3 4 1 lose
2 4 1 3 lose
2 4 3 1 lose

3 1 2 4 lose
3 1 4 2 lose
3 2 1 4 win
3 2 4 1 win
3 4 1 2 win
3 4 2 1 lose

4 1 2 3 lose
4 1 3 2 lose
4 2 1 3 win
4 2 3 1 win
4 3 1 2 lose
4 3 2 1 win

12 win
12 lose

now say your number is 1 then
1 2 3 4 win
1 2 4 3 win
1 3 2 4 win
1 3 4 2 win
1 4 2 3 win
1 4 3 2 win

2 1 3 4 win
2 1 4 3 win
2 3 1 4 lose
2 3 4 1 lose
2 4 1 3 lose
2 4 3 1 lose

3 1 2 4 lose
3 1 4 2 lose
3 2 1 4 win
3 2 4 1 lose
3 4 1 2 win
3 4 2 1 lose

4 1 2 3 lose
4 1 3 2 lose
4 2 1 3 lose
4 2 3 1 win
4 3 1 2 lose
4 3 2 1 win

12 win
12 lose

Okay, but that's only for a single player. Everyone plays with the same box layout, so now we determine if a layout wins with all starting numbers

1 2 3 4 win
1 2 4 3 win
1 3 2 4 win
1 3 4 2 lose
1 4 2 3 lose
1 4 3 2 win

2 1 3 4 win
2 1 4 3 win
2 3 1 4 lose
2 3 4 1 lose
2 4 1 3 lose
2 4 3 1 lose

3 1 2 4 lose
3 1 4 2 lose
3 2 1 4 win
3 2 4 1 lose
3 4 1 2 win
3 4 2 1 lose

4 1 2 3 lose
4 1 3 2 lose
4 2 1 3 lose
4 2 3 1 win
4 3 1 2 lose
4 3 2 1 win

10 win
14 lose
So 41.6% chance of winning.

Basically, if you think about it in terms of swapping boxes, almost like a sorting algorithm, if you swap spots once, you get a win, but any more than one and you get a lose; meaning each extra swap is another box you have to open. So for the original problem any combination that swaps a number more than 50 is going to need more than 50 boxes opened. So then the question becomes how many combinations in total are there versus the combinations of more than 50 box swaps? And you get your probability.

So 100! is a very large number and that is all your possible layouts. Anyone want to finish this train of thought and see what the probability is? Since the number is very large, you could write a problem to look through all the combinations and see how many 50 or less box swap combinations there are versus 100! combinations. I'm guessing it's going to be about 33% difference.

 

[Daddy]

i feel like there's been a lot of focus on the mechanism of the solution strategy but not the actual probabilistic aspect of the problem – which is the actual problem; the problem is not whether you can find a sequence that always ends up with your box or whatever. The question is how do you maximize the probability for the entire prisoner population, and why the is proposed solution strategy even a good one from that point of view.

So going off what I said above, I think it's the best solution you can come up with, simply because it's a sorting problem and the only thing you can analyze is how the boxes are sorted; in other words, analyzing how many times a box gets swapped with another box seems to be all there is to the problem. Could be wrong, but that seems to be the problem.

And if all prisoners started at the same box, your chance of failure is 100% because 50 of those numbers will take more than 50 boxes to open from any given number. Basically, if any prisoner starts at a number that isn't theirs, there is a 50/50 chance that they get their number in less than 50 boxes because you are now potentially following more than one chain of swapped boxes to get to your number (because if you follow a chain that doesn't have your number, you have to pick another chain). So they all have to start at their own number and hope their own number isn't swapped more than 50 times.