> ... it depended on something not stated in the
> problem; in brief it requires multiple interdependent
> participants to adhere to a pre-agreed algorithm
> for searching a data structure whose topology
> they cannot know in advance.
It clearly says: The prisoners have a chance to plot their strategy in advance
That seems pretty clear: the prisoners must pre-agree a strategy to do what they're going to do. Not adhereing to that seems to follow naturally.What am I missing?
Your reference to topology confused me. I thought you were referring to the topology of the cyclic structure(s) induced by the permutation, not to the geometry of the physical arrangement of the boxes.
Now I understand, but I still think theproblem statement is clear.
The problem as stated, or the objection in the HN comment 835216?
I think the problem as stated is perfectly clear, and I thought that when I first met it a few years ago. It boggled me then that it was possible, and it continues to boggle me somewhat even now.
I also heard about it a few years ago, and discovering the solution was mind-blowing! It's stunning that it's possible.
If you're a fan of these types of puzzles please check out my contribution to the field:
http://www.srcf.ucam.org/~te233/maths/puzzles/evenharder.htm...
It took awhile to sink in that the prisoners could use their own memory, instead. Randomly line up, and have each prisoner memorize all prisoners' numbers in line. Then, agree on the numbering structure of the boxes in the room (eg: left to right = 0 to 100).
This fails if the warden is allowed to shuffle the boxes before each prisoner selects (not likely). It also fails if the room were rotationally symmetric, and each prisoner was brought in from one of two entrances. This way he would be unable to identify the "left" end of the line of boxes. (Much more likely, were I warden).
The solution is interesting and worthy, but the problem as written is poorly stated. I hit the right idea while I was thinking about it but then rejected it because it seemed like an unjustified assumption. More than one of these seem to depend on the vagueness or incompleteness of the problem specification resulting in a meta-solution rather than a formal one.