Hacker News Reader

Comment by phkahler | Hacker News Reader

I don't understand the answer at all. Are they suggesting that the prisoners have somehow labeled the boxes? Or do they agree to assign names to the boxes via some other way - like make an alphabetic list of prisoners and assume that is the order of the "names on the boxes"? I suppose I just answered my own question, but I'm still not sure ;-)

View on HN

One assumption not explicitly explained is that the prisoners can identify the boxes by their order, since they are arranged in a line. So, the prisoners first agree among themselves that box number x should correspond to which prisoner, and vice versa. So now, each box contains a name, which points to another box at a certain position, which contains another name, ad infinitum, until the prisoner finds his name. It is guaranteed that he will, because of the relationship between permutations and cycles.

It is interesting that this question is regarded as the most math intensive. I myself was spoiled the solution a few years ago, but I have the impression that the challenge is in observing the correct algorithm rather than calculating the probability. Maybe the author felt that one needs mathematical insights in order to see the solution out of the blue.

Yes, not everyone knows that permutations decompose uniquely as products of disjoint cycles.

>I have the impression that the challenge is in observing the correct algorithm rather than calculating the probability

I've got a stats PhD and I guessed the solution but couldn't calculate the probability of having a max cycle length of 50 or less. To be fair, the calculation isn't hard once you see it, but it's not trivial either.

The 30% figure threw me since I know the probability of a random permutation having a fixed point is 1/e (just over 30%), so I went looking for ways to link the cycle length to the Poisson distribution.

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.

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.

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.

Yeah, they memorize their own random ordering. Alphabetic is risky because the warden might guess that strategy and purposefully set up the boxes so it doesn't work.

Reply on news.ycombinator.com