Seven Puzzles You Think You Must Not Have Heard Correctly

http://www.math.dartmouth.edu/~pw/solutions.pdf

by mhb • 17 years ago

51 35 17 years ago

math.dartmouth.edu

michael_dorfman• 17 years ago

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

tome5• 17 years ago

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

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

calambrac2• 17 years ago

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

dreish2• 17 years ago

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.

anigbrowl7• 17 years ago

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.

anigbrowl7• 17 years ago

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

dreish2• 17 years ago

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.

hawk• 17 years ago

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

anigbrowl7• 17 years ago

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.

RiderOfGiraffes3• 17 years ago

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?

tome5• 17 years ago

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

anigbrowl7• 17 years ago

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.

sam_in_nyc• 17 years ago

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

muerdeme3• 17 years ago

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

tome5• 17 years ago

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

muerdeme3• 17 years ago

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.

calambrac2• 17 years ago

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

jongraehl• 17 years ago

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

MaysonL• 17 years ago

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

jibiki• 17 years ago

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

Dove• 17 years ago

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!

cousin_it• 17 years ago

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!

Seven Puzzles You Think You Must Not Have Heard Correctly

Related Stories