Hacker News Reader

Comment by SilasX | Hacker News Reader

I don't understand: the solution text claims that some permutations are guaranteed to work every time[1]. But you still have to initially land in one of "your" cycles, right?

[1] "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."

View on HN

You always land in "your" cycle, because you start with the box with your name on it.

All sequences of box-opening that use the method described must eventually cycle, because both box-to-name mappings are 1-to-1. Because it's a cycle, the sequence must eventually lead back to the box you started with. Since you start with the box with your name on it, then whatever cycle you landed it, it definitely contains the box with your name on it, because that box is the one that completes the cycle. The only question is whether the cycle is length-50 or less.

I guess that's what I'm confused about: when we start, the boxes we map our names to have nothing to do with the name in the box. Just because my cycle includes the box I got assigned to, doesn't mean that cycle includes the box with my name inside it. If my name maps to 89, then sure, I accept 89 is a LT-50 cycle, but why does it mean that that cycle actually contains my name (as opposed to the box we assigned me to)?

Think about how you will get back to the box you got assigned to. Like what do you have to see in order to return to box 89, where you started?

Ah, okay, that makes more sense. So the solution is to impose a random ordering on the (1-100 random numbers assigned to the) boxes that ensures you will return to the first one you picked, and that the one that points to your initial pick (or your initial pick itself) has your name in it.

This ordering then partitions the boxes into cycles where each prisoner is in their cycle, and has a low chance of having 50-sized cycles.

Still mesmerized at how the choice of query can improve your chances like that without accumulating information.

But why would that matter? You don't know 89 has your name in it, because the numbers were randomly assigned to random people in the first place. You would just draw the name associated with box 89, which is not necessarily your name.

Whatever box you open, you take the name inside and go to the number you associated with that name. So when you end up at box 89, the last box you opened must have had your name inside. So you will have found your name, provided you got there in under 50 steps.

Reply on news.ycombinator.com