Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by gambiting on Monday August 29, 2016 @10:52AM (#12382206)

Every prisoner assigns every box a random name from the list. Boxes cannot be modified in any way, so every prisoner has to do it on their own. The (unexplained) assumption here is that each prisoner can do that somehow, either in their head or on a piece of paper. It doesn't matter that every prisoner has their own unique assignment of names to boxes.

The crucial part here is that it's not guaranteed to work - but it gives prisoners 30% chance to survive, as opposed to some infinitesimally small number if each picks 50 boxes on random.

[ Parent | on HN ]

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by captaincanoe on Monday August 29, 2016 @11:06AM (#12382311)

If each prisoner randomly labels the boxes in their own (presumably independent) manner, then this strategy fails miserably. In fact, it's equivalent to each prisoner choosing 50 random (unique) boxes.

The solution specifies that "the prisoners must first agree on a random labeling of the boxes by their own names." This is necessary.

[ Parent | on HN ]

Re:Seven Puzzles You Think You Must Not Have Heard Correctly... by hexane360 on Monday August 29, 2016 @05:40PM (#12385597)

If each prisoner has their own ordering, it's exceedingly likely that one of those orderings will have a 51-cycle.

This strategy only works with one common dictionary. You have the same individual odds, but you've linked each person: each member of a cycle succeeds or fails together.

If it wasn't decided beforehand, you could just make up the ordering as you go. This gives exactly the same odds as random selection.

[ Parent | on HN ]