Seven Puzzles You Think You Must Not Have Heard Correctly | Hacker News Reader

Seven Puzzles You Think You Must Not Have Heard Correctly

math.dartmouth.edu

51 pointsmhb38 comments

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.

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?

It's not clear that they can distinguish the boxes in advance, but apart from that, I think it's perfectly clear.

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

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

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.

Lines are a special type of curve - a straight curve. This precise and simple mathematical definition precludes such confusion.

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

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.

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

In the case of the first, I was able to get some pretty good odds -- but nowhere near what the problem claims. The solution is brilliant, but requires a little more abstract algebra and combinatorics than I was able to lay my hands on quickly.

The second problem is surprisingly difficult, and more annoyingly, the 2D case offers no guidance for the 3D case. Even more annoyingly, the solution, while obviously correct, is unenlightening. I hate unenlightening proofs.

The third problem suffers from the abstract problem statement and unclear mechanic; I had to read the solution to understand the problem, which is too bad. It's a wonderful problem. Fortunately, understanding the solution wasn't exactly a whole lot simpler than solving the problem might be, so I had that as compensation. I offer the following (simpler) restatement in the hope that it will allow someone else to enjoy the problem:

There is a town where each member has on his forehead a blue or red dot. If on any given day he figures out which it is, he dies in his sleep that night. On one particular morning, five of them--all with blue dots, unbeknownst to them--are standing on a street corner when a stranger walks by. "Well," he says, "I see more than one blue dot is out this fine morning!" Prove that all five die in their sleep before the week is over.

(If you can do that, the generalization is obvious -- so stating the problem in a general way only serves to obscure the terms.)

The rest of the problems rapidly lost my interest . . . so I'd say they were well arranged.

Thanks for an enjoyable waste of an evening!

The second problem is really good. I just thought up a solution that, though more complex, seems to me much less mysterious, and the 2D case does shed guidance on 3D.

One-dimensional case:

    a1 < a2

Two-dimensional case:

    a1*b1 < a2*b2 (area)
    a1+b1 < a2+b2 (sides projected outwards, triangle inequality)

Three-dimensional case:

    a1*b1*c1 < a2*b2*c2 (volume)
    a1*b1+a1*c1+b1*c1 < a2*b2+a2*c2+b2*c2 (surface area, projected outwards)
    a1+b1+c1 < a2+b2+c2 (our problem)

Notice the pattern already? If one N-dimensional box lies inside the other, the inequality holds for all elementary symmetric polynomials of box dimensions.

http://en.wikipedia.org/wiki/Elementary_symmetric_polynomial

To prove it, we need only notice that the symmetric polynomial of degree M is proportional to the average volume of the M-dimensional "shadow" of the N-dimensional box, averaged over all projection directions uniformly. (To convince yourself of that, work through the two-dimensional case.) On the other hand, if a box lies inside another box, each "shadow" of the smaller box lies within the corresponding "shadow" of the bigger box. Done!

I'm all for thinking outside the box, but the whole point of a puzzle is to set up a set of constraints and work your way from there. The solution to #1 seems to contradict that spirit - without spoiling it, it's true the description didn't say they couldn't do what they need to do, but it also didn't say they couldn't riot, kill all the guards, and just escape to avoid playing the game altogether...

I fail to see how the solution to #1 contradicts the plain meaning of the constraints. I think it's an ingenious and surprising result.

I guess it depends on how you interpret 'lined up'. What if the room is circular, the table runs around the circumference, and you enter the room through a trapdoor in the center? Then your entry point to the list is effectively randomized and on any given trial the algorithm will work no better than chance.

I believe the standard interpretation of 'lined up' is 'in a line', as in a 'straight curve', which disallows your otherwise ingenious foil.

True. But as soon as I thought of the circle, I said to myself 'ah, the idea that it's a straight line is exactly the sort of assumption that you gets you into trouble!' so I threw the whole solution out.

I figured a straight line would be equivalent to a random arrangement with each of the boxes being numbered, so I assumed the vagueness was designed to lead one into making a foolish assumption about their ordinal presentation. Maybe I'm paranoid :-)

Well, there are actually two unstated preconditions that need to hold for proposed strategy to work:

1) every prisoner uses the same entry (with the same reference frame in respect to boxes)

2) there are no changes in the arrangement of boxes between prisoner visits (this is extra requirement, as it includes wardens not doing any rearrangements in the meanwhile)

But otherwise, the strategy could be extended for arbitrary topologies - just state additional algorithm for defining starting point of labeling and then use a deterministic rule telling which box would be the next one.

For example, for circular arrangement - start at 12:00 and go clockwise.

Or, for arbitrary random arrangement - start at upper left box and then proceed in (axis-aligned) grid: leftmost->rightmost->down to next leftmost->repeat.

I fully agree. The described solution is easily defeatable without violating the other conditions.

Defeatable? What on Earth does that mean? The goal of these puzzles is to find a solution, not to foil the given solution. "Lined up on a table" has a common-sense meaning. Everything else in this puzzle and the solution is purely based on the common-sense meaning of the words used.

Well, given my erroneous thinking about lines vs. curves (something you sometimes see exploited in other puzzles), when I say 'defeatable' I mean from the point of view of the warden, who would be seeking to minimize the prisoners' chances of success. You know, 'mwuhhahaha! I never said they were in a straight line' or indeed 'mwuhahaha, I never said we were in Euclidean space!'.

I disagree, this is a great puzzle and is pretty well specified.

Six of those were mind-blowers, but the solution to one should be obvious to most hackers.

I call BS on Problem 1: it's bait and switch!

The answer to the puzzle #1 is simply totally incorrect: how long the permutations are has nothing to do with whether your name is in any of the boxes in the permutation that the prisoners start with your name.

EDIT: After thinking about, and trying a few small {try 4 boxes) examples, I'm not so sure [i.e. I guess I blew it].

> The answer to the puzzle #1 is simply totally incorrect: how long the permutations are has nothing to do with whether your name is in any of the boxes in the permutation that the prisoners start with your name.

The answer is correct. Your name has to be in the cycle started with your box, this follows from the fact that permutations are bijections. It is impossible to have something like:

  0->1->2->1

(Because then 1 would be in two boxes at once, which is impossible.)

If you like the Random Native puzzle, try this one for size!

http://www.srcf.ucam.org/~te233/maths/puzzles/evenharder.htm...

"post offices and currier services" - http://en.wikipedia.org/wiki/Currier

Correction to the Roger Federer problem: the setting must be the U.S. Open for the solution to make any sense.

I don't get that at all. Why? The scoring at the US Open is not different to Wimbledon as far as I know.

The U.S. Open is the only grand slam tournament that uses final set tiebreaks. Hence the marathon 5th set (16-14) between Roddick and Federer at this year's Wimbledon.

Ah I did not know that, thanks!

But the final (i.e. fifth) set is never reached in the solution. At Wimbledon it is entriely correct that you can win the match in three or four sets by winning the third or fourth set in a tie-break. There is not a problem with the solution as stated.

"Final" means the set that will end the match, not necessarily the fifth set.

It may do elsewhere but it doesn't at Wimbledon.

It was a funny reference to Federer blowing it against his final opponent at this year's US Open, despite dominating the whole tournament.

Reply on news.ycombinator.com