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.
> ... 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 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.
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.
Notice the pattern already? If one N-dimensional box lies inside the other, the inequality holds for all elementary symmetric polynomials of box dimensions.
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...
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.)
[+] [-] anigbrowl|16 years ago|reply
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.
[+] [-] RiderOfGiraffes|16 years ago|reply
What am I missing?
[+] [-] sam_in_nyc|16 years ago|reply
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).
[+] [-] Dove|16 years ago|reply
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|16 years ago|reply
One-dimensional case:
Two-dimensional case: Three-dimensional case: 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!
[+] [-] calambrac|16 years ago|reply
[+] [-] dreish|16 years ago|reply
[+] [-] hawk|16 years ago|reply
[+] [-] anigbrowl|16 years ago|reply
[+] [-] michael_dorfman|16 years ago|reply
[+] [-] MaysonL|16 years ago|reply
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|16 years ago|reply
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:
(Because then 1 would be in two boxes at once, which is impossible.)[+] [-] tome|16 years ago|reply
http://www.srcf.ucam.org/~te233/maths/puzzles/evenharder.htm...
[+] [-] jongraehl|16 years ago|reply
[+] [-] muerdeme|16 years ago|reply
[+] [-] tome|16 years ago|reply
[+] [-] taw|16 years ago|reply
[deleted]