6 ms·
Seven Puzzles You Think You Must Not Have Heard Correctly
- tome 17y agoIf you like the Random Native puzzle, try this one for size! http://www.srcf.ucam.org/~te233/maths/puzzles/evenharder.html http://www.srcf.ucam.org/~te233/maths/puzzles/evenharder.htm...
- calambrac 17y agoI'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...
- dreish 17y agoI fail to see how the solution to #1 contradicts the plain meaning of the constraints. I think it's an ingenious and surprising result.
- anigbrowl 17y agoI 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.
- req2 17y agoI believe the standard interpretation of 'lined up' is 'in a line', as in a 'straight curve', which disallows your otherwise ingenious foil.
- anigbrowl 17y agoTrue. 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 :-)
- bd 17y agoWell, 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.
- deleted 17y ago[deleted]
- dreish 17y agoThat's ridiculous. Proposing a nonsense solution certainly doesn't risk giving anything away. (You claim that there is a 100% likelihood the warden will cooperate and put the names in the boxes the prisoners request?) If you think there's something wrong with the solution provided, why not just come out with it, and write "SPOILER WARNING" before it? I suspect you're misunderstanding something, though.
- calambrac 17y agoYou're right, I misread it as "The prisoners get the Warden to label the boxes randomly", with the same implicit assumption as anigbrowl, that the prisoners don't have enough information beforehand to assign an order to the boxes.
- req2 17y agoThe warden is not compelled to cooperate.
- anigbrowl 17y agoI fully agree. The described solution is easily defeatable without violating the other conditions.
- dreish 17y agoDefeatable? 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.
- anigbrowl 17y agoWell, 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!'.
- hawk 17y agoI disagree, this is a great puzzle and is pretty well specified.
- anigbrowl 17y agoFun 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.
- RiderOfGiraffes 17y agoI 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?
- tome 17y agoIt's not clear that they can distinguish the boxes in advance, but apart from that, I think it's perfectly clear.
- RiderOfGiraffes 17y ago> 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.
- tome 17y agoI 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.html http://www.srcf.ucam.org/~te233/maths/puzzles/evenharder.htm...
- muerdeme 17y agoCorrection to the Roger Federer problem: the setting must be the U.S. Open for the solution to make any sense.
- tome 17y agoI don't get that at all. Why? The scoring at the US Open is not different to Wimbledon as far as I know.
- muerdeme 17y agoThe 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.
- tome 17y agoAh I did not know that, thanks!
- andrew1 17y agoBut 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.
- calambrac 17y agoIt was a funny reference to Federer blowing it against his final opponent at this year's US Open, despite dominating the whole tournament.
- michael_dorfman 17y agoSix of those were mind-blowers, but the solution to one should be obvious to most hackers.
- jongraehl 17y ago"post offices and currier services" - http://en.wikipedia.org/wiki/Currier http://en.wikipedia.org/wiki/Currier
- taw 17y agoHere's the score: 1. Mind-blowing 2. Seems like too much work in 3D 3. This is total bullshit, the induction argument is completely bogus, and what you said doesn't provide any new information to them. 4. Trivial 5. It's just Diffie-Hellman, so you've probably already seen it in some crypto textbook. Pretty cool if you haven't seen it before. 6. How exactly tennis works again? 7. Trivial So one really good one, five not so good ones, and one completely wrong.
- MaysonL 17y agoI 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 17y 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 17y agoIn 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 17y agoThe 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 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!