Seven Puzzles You Think You Must Not Have Heard Correctly

Re:Seven Puzzles You Think You Must Not Have Heard Correctly by Dove on Tuesday September 22, 2009 @01:41AM (#836364)

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!

[ Parent | on HN ]

Re:Seven Puzzles You Think You Must Not Have Heard Correctly by cousin_it on Tuesday September 22, 2009 @04:27AM (#836552)

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!

[ Parent | on HN ]