News for hackers. Stuff that matters.
Re:Seven Puzzles You Think You Must Not Have Heard Correctly by anigbrowl on Monday September 21, 2009 @02:49PM (#835216)
Fun paper, but I got pissed off with the first one because 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.

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.

Re:Seven Puzzles You Think You Must Not Have Heard Correctly by RiderOfGiraffes on Monday September 21, 2009 @03:18PM (#835284)
I don't understand your objection ...

    > ... 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?

Re:Seven Puzzles You Think You Must Not Have Heard Correctly by anigbrowl on Monday September 21, 2009 @03:26PM (#835313)
Quite correct. But when I was imagining it, I began thinking of different ways to 'line up' the boxes and it's not clear to me from the problem statement that the layout is predictable in advance. See below for why (I think) a circular arrangement would defeat the strategy. Lines can be curved, and curves may be closed.
Re:Seven Puzzles You Think You Must Not Have Heard Correctly by req2 on Monday September 21, 2009 @03:32PM (#835326)
Lines are a special type of curve - a straight curve. This precise and simple mathematical definition precludes such confusion.
Re:Seven Puzzles You Think You Must Not Have Heard Correctly by anigbrowl on Monday September 21, 2009 @03:40PM (#835344)
Can't argue with that. I guess I'm thinking of those puzzles that say things like 'can you draw a line that passes through all these points', and when you can't, the answer turns out to be that it's not a straight line. I'll leave my wrong arguments up for educational purposes :-)
Re:Seven Puzzles You Think You Must Not Have Heard Correctly by RiderOfGiraffes on Monday September 21, 2009 @04:02PM (#835401)
Ah, so what I'm missing is that you think the boxes may be arranged in other than a straight line.

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.

Re:Seven Puzzles You Think You Must Not Have Heard Correctly by tome on Monday September 21, 2009 @03:20PM (#835292)
It's not clear that they can distinguish the boxes in advance, but apart from that, I think it's perfectly clear.
Re:Seven Puzzles You Think You Must Not Have Heard Correctly by RiderOfGiraffes on Monday September 21, 2009 @03:23PM (#835307)
> I think it's perfectly 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.

Re:Seven Puzzles You Think You Must Not Have Heard Correctly by tome on Monday September 21, 2009 @03:39PM (#835340)
I agree with you that the problem as stated is perfectly clear. I thought the statement lacked a little clarity about how distinguishable the boxes were for the prisoners that haven't seen them before, but on second reading I think that's clear too.

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...

Re:Seven Puzzles You Think You Must Not Have Heard Correctly by sam_in_nyc on Monday September 21, 2009 @04:08PM (#835417)
What got me at first was reading the solution and thinking: "Oh, so they're allowed to label the boxes beforehand? Lame." I assumed by "label" the solutions meant "physically write on the box."

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).