12
$\begingroup$

I met a puzzle, which is basically well known 100 Prisoners' Names in Boxes , but... it has an algorithm, which gives prisoners 100% chance to survive!

This is achieved by a small change in the procedure:
Prisoners can invite a friend, who visit the room before the first prisoner and is allowed to check out all boxes and switch places of two names in them.
That's it. The prisoners and the friend have a chance to plot their strategy in advance, but no communication is allowed after beginning of the procedure.

How 100% survival can be reached here is quite obvious for those who read the linked topic, but anyway here is it:

The numbers from 1 to 100 is given to each prisoner (you can read "number" as a "name") and to each box. The friend must find all chains of numbers like "Box A has number B -> Box B has number C -> ... -> box X has number A". There can be only one chain of length more than 50. If the friend finds it he must switch places of two distant numbers in the chain. In that case the chain will be divided into two chains of length less than 50.
Then all prisoners just must start from the box with their number and follow the chain until they reaches the box, which contains they number. Since there won't be any chain longer than 50 all of them will succeed.

As you can see, we got quite nice puzzle on it's own, which can be given even to a child, who can't do complicated probability calculations.
So I started to wonder - What are other possible changes in the initial 100 Prisoners' Names in Boxes procedure you can make that similarly lead to 100% chance of survival? I mean really small changes, hopefully even smaller than the given example.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I just don't get why you'd want all the prisoners to escape.. They're there for a reason! -on a serious note, any change that makes it impossible for chains of 50+ to exist would obviously do it, but perhaps there are other solutions where you play with ordering or information given out. $\endgroup$
    – DrunkWolf
    Oct 19, 2015 at 6:38
  • 1
    $\begingroup$ My favorite version of this problem is the infinite one! See here for the question and here for a clearer explanation. $\endgroup$
    – Alexis Olson
    Aug 2, 2016 at 4:53
  • $\begingroup$ @AlexisOlson, thanks, that's what I looked for. $\endgroup$
    – klm123
    Aug 2, 2016 at 6:11
  • $\begingroup$ This 'small change in the procedure' changes the original puzzle to something very similar to this one puzzling.stackexchange.com/questions/23150/…. $\endgroup$
    – oleslaw
    Oct 27, 2016 at 9:25
  • $\begingroup$ @oleslaw, it is not even similar, it is Exactly the same. $\endgroup$
    – klm123
    Oct 27, 2016 at 10:18

2 Answers 2

Reset to default
2
$\begingroup$

I thought about this in the 100 prisoners boxes thread, here's what I came up with:

The first prisoner is allowed to restart the experiment (as many times as he wants) at the end of his turn, the boxes will be reshuffled before he reenters the room (he will not be able to communicate with other prisoners while the room is reset)

To win, just use this variation of the same strategy:

  • if the first prisoner don't find his name, he asks for a reset obviously
  • if he finds his name by opening less than 50 boxes, he asks for a reset (because that gives a chance of a >50 length cycle)
  • if he finds his name by opening exactly 50 boxes, he knows for sure everyone will find their own name in at most 50 tries (if one cycle is of length 50, no other cycle can be > 50)

Downside is that could take a while...

Improve this answer
$\endgroup$
3
  • $\begingroup$ Should only take on average about 3 shuffles. $\endgroup$
    – Trenin
    Oct 27, 2016 at 13:50
  • 1
    $\begingroup$ Nice try, but restarting as many times as prisoner wants, means that you allow prisoner to chose content of 50 boxes. This makes the task trivial. Just divide prisoners in two groups, first group always check boxes #1 - #50, which the first prisoner set up for them, the 2nd group - check the other 50 boxes. $\endgroup$
    – klm123
    Oct 27, 2016 at 15:33
  • $\begingroup$ Yes the problem of calculating the success percentage is moved to calculating the average times it takes to succeed because without constraints a brute force method is allowed. $\endgroup$
    – Guillaume86
    Oct 27, 2016 at 16:15
0
$\begingroup$

Could they still invite a friend who:

looks in each box and places them in order using their contents (alphabetically or numerically)? Prisoners could simply enter the room and choose the box that is in the order on the table corresponding to their assigned name/number.

In the case they don't precisely know all the other prisoner's names/numbers, they can still choose a central box and move left/right depending on what they found, and keep choosing a central box in that left/right set until they find their name.

I guess it's not a small change, but

there's a very small chance you only have to move two boxes. :P

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.