14 ms·
Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
- Ensorceled 10y ago<spoiler>For #1, I didn't hear correctly because I didn't understand that the clearly insane and cruel warden would let the prisoners label the boxes before hand :-/
- Avshalom 10y agoYou don't actually need to label them you just need all the prisoners to be able to memorize which name is associated with which box, Alice's box is the first on the left, Bob's the second etc... Then when Zach. Z. Z. Vanderwall opens "his box" and finds the name Bob he follows procedure. You need a minimal perfect hash function but it's a thing that can be done, especially because prisoners in these sort of conundrums always have fantastic memories and mental math facility. https://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_perfect_hash_function https://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_...
- isolli 10y agoStill, I didn't hear correctly either: I thought there would be 100 identical boxes lined up in a row by the warden's assistant.
- maxerickson 10y agoThe solution still works. The prisoners have agreed on a mapping between their names and the order of the 100 boxes. That mapping is what they rely on to inspect the boxes, the boxes don't need actual labels. The problem statement makes it clear they can communicate prior to starting the game.
- Tobold 10y agoAnd they all do what you, The Nerd, say. Prisoners are known to be well-behaved and respect Nerds! /s
- greenshackle 10y agoFrom my experience as a nerd playing werewolf with non-nerds I'm afraid you're right. Me: "Here's a plan that will defeat the werewolf in any case, even if I am the werewolf" Them: "That sounds complicated, therefore suspicious, let's hang him"
- ikeboy 10y ago>fantastic memories and mental math facility. If you assume the axiom of choice and allow them to memorize arbitrary uncountable elements, you can get more interesting puzzles (and also go insane). https://cornellmath.wordpress.com/2007/09/13/the-axiom-of-choice-is-wrong/ https://cornellmath.wordpress.com/2007/09/13/the-axiom-of-ch...
- Ensorceled 10y agoDoh! Of course. But now the recommended solution is really overkill ...
- mkagenius 10y agoThank god I could solve "Love in Kleptopia". Would have been embarrassing being a founder of a security company.
- cyborgx7 10y agoI'm mad at myself for not managing to figure this out myself. I guess i made more assumptions about the limitations than there were in the description of the problem.
- heartbreak 10y agoI think you'd enjoy The Code Book by Simon Singh.
- deleted 10y ago[deleted]
- JackFr 10y agoSame. It was not clear that multiple padlocks can be added to the box.
- deleted 10y ago[deleted]
- semiel 10y agoIt took me way too long for this reason. I got it instantly once I realized I had made that limitation up. I feel like there is some sort of lesson, here.
- Natsu 10y ago> I guess I made more assumptions about the limitations than there were in the description of the problem. This accounts for some high percentage of the failures in figuring out brain teasers :)
- StavrosK 10y agoI knew "the" solution was something DH-like, but my solution was: Maria mails Jan one of her padlocks, and he mails her the ring back in a box that's locked by that padlock. ...I think others are overcomplicating this.
- Tobold 10y agoI am so bad at this. Also, apparently I don't know the first thing about tennis.
- JoeAltmaier 10y agoThe 'dot-town suicides' is a more general version of a puzzle I know, "The Island with Blue-Eyed People". The solution is an induction, which is unusual in these kinds of problems.
- adium 10y agoWhy can't the visitor say "There are X red, X blue, and 1 yellow?" No one knows about the yellow, thinks it is themself, they all commit suicide on the spot.
- JoeAltmaier 10y agoThat sounds about right. But the problem statement doesn't permit the information to be a lie? The info could be "somebody has blue eyes!"
- adium 10y agoThe comment elaborated on the explanation of "non-trivial" and didn't explicitly say you can't lie. Right? Or am I not hearing this correctly? Some of the questions incorporate a "new idea" or allow you to change elements. Triangle boxes, prisoners who can make requests, tired tennis players.... I introduced a yellow dot or am I supposed to change the variables to two?
- _archon_ 10y agoThere's a discrepancy between the number of visible blues and the number given. Say the person is a blue and doesn't know it. They can count b-1 blues on everyone else. Hearing "r reds, b blues, 1 yellow," he knows he must be either blue or yellow. He doesn't know which. Everyone survives. Edit: had a paren instead of opening quote.
- adium 10y agoI'm also thinking it would need to be at least a couple hundred people to be classified as a town. Which then the odds of someone subconsciously counting a number that high in their head is unlikely. In a classroom with 30 people right now and I couldn't tell you how many of each gender there are unless I actively try. If that meant certain death, why would I count?
- kuriho 10y agoI have always been a fan of the Pirate game puzzle. https://omohundro.files.wordpress.com/2009/03/stewart99_a_puzzle_for_pirates.pdf https://omohundro.files.wordpress.com/2009/03/stewart99_a_pu...
- oli5679 10y agoI'm have some trouble understanding the solution to the 3 natives puzzle. Is the objective to find the road guarded by the truth teller? SPOILER BELOW The solution suggests Q1) --> A Q1): Is B least likely to tell the truth out of B and C? If yes ask Q2 --> B, If no, ask Q2 --> C Q2): If I were to ask you does your road lead to the truth village, would you say yes? If yes, you know where the truth village is. If no, you would know the person you are questioning in the liar, but both of the other two could be the truth teller or the random answerer? For example, if A is the random answerer and randomly selects 'truth', or if A is the truth teller, they will both direct you to the liar for Q2. Let me know where I've gone wrong.
- agf 10y agoThere are only two roads and one village, and the problem is to find out which of the roads lead to the village. Forget about "guarding" and the "truth village". If you ignore the random answerer for a second, then you ask "if I were to ask you if this road leads to the village, what would you say?". Let's call this the original question. The answer will be trustable, because the truth teller will tell the truth, and the liar will lie about a lie, making the result the truth as well. Now we introduce a new question, and a third answerer -- random. Since we know we can solve the problem with only the original question and original two natives, the goal of this question is just to eliminate the random answerer. The solution given in the article uses this new question in two ways. One, by asking it of one native and not ever asking that native the original question, if the native we happen to ask is the random answerer, we know we won't ask the original question of that answerer, so what they answer doesn't matter -- either way, we'll end up with the liar or truth teller to ask the original question of. So we only need to design the new question assuming the one we ask it of is not the random answerer. So now we're back to asking a "double question", resulting in a truth about a truth or a lie about a lie. You ask the question you stated, knowing that the native identified as "least likely to tell the truth" will never be the random one, due to truth-about-truth, lie-about-lie, or due to the random answerer being neither B nor C.
- oli5679 10y agoAh ok, if there are 2 roads and 3 people then the question makes complete sense.
- n4r9 10y ago"Learning a single variable polynomial" also falls into this camp, although partly due to learned bias. https://jeremykun.com/2014/11/18/learning-a-single-variable-polynomial-or-the-power-of-adaptive-queries/ https://jeremykun.com/2014/11/18/learning-a-single-variable-...
- thomasahle 10y agoThis is beautiful.
- jfries 10y agoSPOILER 1 Names in boxes I don't understand how this works. The answer says it works to a certain percentage if there are no cycles longer than 50. But even if chance has it that there are two cycles of length 50. Then it seems the chance would be very large that one of the 100 prisoners would en up in the "wrong" loop and thus not find their name?
- deleted 10y ago[deleted]
- hundt 10y agoIt's because you start with the box labeled (via the initial random labeling) with your name. If you cycle back to it then it means that you found your name on a piece of paper, since the next box you open is always the one matching the piece of paper in the last box. So it is impossible to start in a cycle that doesn't include your name.
- jfries 10y agoAh right, that's clever. Thanks for the explanation!
- rntz 10y agoCouldn't I start in a "tail" leading to a cycle that doesn't include my name? Suppose my name is "A", and I proceed: check box A - read name B; check box B - read name C; check box C - read name B and now I'm in a B-C loop, and will never find my name.
- agf 10y agoRe-read your scenario -- you have both box A and box C containing name B, but the problem statement says each name appears only once. So you can't get into cycles like this.
- rntz 10y agoAh, of course! That guarantees there are no "tails"; every name (& box) is part of exactly one cycle. And this is then a property of cycles of permutations generally. Thanks!
- deleted 10y ago[deleted]
- panic 10y ago#2 is super interesting! I wonder if it generalizes to higher dimensions.
- alanbernstein 10y agoI don't quite follow the solution, can anyone explain a bit more? What's the motivation for considering large epsilon?
- yorwba 10y agoThe rigorous version would be: 0 < (Vol(Bε) - Vol(Aε))/ε² = ((a+b+c) - (a'+b'+c'))π + 2((ab + ac + bc) - (a'b' + a'c' + b'c'))/ε + (abc - a'b'c')/ε² The limit for ε to infinity must be >= 0 and is ((a+b+c) - (a'+b'+c'))π, therefore a+b+c >= a'+b'+c'. "large epsilon" is a standard way to express "consider the asymptotic behavior for epsilon to infinity and you will see what I mean".
- alanbernstein 10y agoThanks, I get that it means asymptotic behavior - that's the thing I don't get the motivation for.
- panic 10y agoI think the intuition is that we want to focus on the edges of the box (where the lengths sum together like the answer we're looking for), not the volume (where the lengths multiply together and cause problems). So we expand the edges until they completely dominate the equation.
- mgillett 10y agoOne that I heard last week: There is an 8x8 checkerboard in a room with a coin placed on each square. Each coin is either facing heads or tails up, and the face is determined randomly. Before you can inspect the board, a "master" comes in, picks a square of interest, and must make a manipulation to the board by flipping one of the 64 coins. He then exits the room. You are now allowed to enter, and must read out which square of interest the master chose by inspecting the state of the board. There is a strategy that is guaranteed to work for all possible configurations of the board.
- dpark 10y agoEither I'm somehow missing some critical piece of this puzzle or your description is. The master could pick a square at random, leaving you with a board (and likelihood of success) that is still completely random. Are you supposed to be collaborating with the "master"?
- agf 10y agoI think you're referring to this puzzle: http://datagenetics.com/blog/december12014/index.html http://datagenetics.com/blog/december12014/index.html The version you gave is missing information and so can't be solved as stated.
- CPLX 10y agoI had to read that like 11 times before I started to get the underlying principle. That's amazing.
- hexane360 10y agoIn a very similar vein, try this one: https://youtu.be/N5vJSNXPEwA https://youtu.be/N5vJSNXPEwA
- kristjansson 10y agoThank you for posting this. I read the parent several times trying to figure out if they were mistaken or I was dense.
- deleted 10y ago[deleted]
- apricot 10y agoPeter Winkler's books of mathematical puzzles ("Mathematical Puzzles" and "Mathematical Mind-Benders") are top-notch and highly recommended. You will learn something there even if you've read dozens of puzzle books before.
- deleted 10y ago[deleted]
- cousin_it 10y agoI think there's a simpler solution to boxes in boxes. Assume that the outer box is axis-aligned. Project both boxes onto the X axis, so they become one-dimensional. It's easy to check that the "projected perimeter" of the inner box is smaller. Repeat for axes Y and Z. From that and the triangle inequality, the result follows.
- bzbarsky 10y agoCan you expand on this last step? it's not obvious to me what you're applying the triangle inequality to and why it gives the desired result.
- cousin_it 10y agoThe length of a line segment can't be greater than the sum of its projections onto all three axes. Therefore the "perimeter" of the inner box can't be greater than the sum of its projections. But that sum is bounded from above by the "perimeter" of the outer box (which is equal to the sum of its own projections, because the outer box is axis-aligned).
- pfedak 10y agoI'm having trouble with your "therefore" conclusion. The projection of the perimeter of the inner box could easily be shorter than the sum of the lengths of the projections of each edge. It seems like you need a less obvious (to me, anyway) statement about the projection of a collection of lines.
- cousin_it 10y agoBy projected perimeter I mean the sum of lengths of projections of all edges. I'm not canceling them out or anything. Think of the box as a graph, its projection is another graph that happens to lie on a straight line, but we can measure the sum of its edges regardless. It's not completely obvious why the projected perimeter of the inner box is bounded by the projected perimeter of the outer box, but it's a statement about one-dimensional segments that's easy enough to check.
- iliis 10y agoAh, I love these kind of puzzles! Here's another one, similiar to the first one (Names in Boxes). Apologies for any incorrections in advance. There are 100 prisoners. At random times one prisoner is chosen uniformly at random and led into a room with a single lamp. The prisoner can choose to switch it on or off or leave it as the last visiting prisoner left it. Apart from the state of the lamp he must leave the room unchanged. After visiting the room, each prisoner is asked if every prisoner has visited the room by now. If he answers 'Yes' and indeed everyone has been to the room at least once, then everybody is freed immediately. Otherwise they are all executed ;) He can answer 'I don't know' without any consequences. Apart from the lamp being on or off the prisoners have no way of communication at all, but of course as is customary in such puzzles they can plot a strategy in advance and everybody is a perfect logician. So, to clarify: The goal is for one prisoner to be 100% sure that everybody has been to the room at least once. The "easiest" solution would simply be to wait a few billion years (it's an abstract puzzle, they are all immortal anyways ;). But of course there is a more elegant solution that terminates earlier. Also, as the time for a visit is chosen at random a prisoner has no way of knowing who the previous person in the room was. It might just as well have been himself! As there is some randomness involved, it is theoretically possible that the goal state never happens. Just assume that in the limit everybody will have visited the room infinitely often ;) In other words: Implement synchronization between 100 threads with only one bit of shared memory and completely random scheduling.
- dsugarman 10y ago>The "easiest" solution would simply be to wait a few billion years Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. Of course the probability will get higher and higher that everyone was in the room once if it was completely random but that probability will never be 100%. I know of two legitimate answers to this problem, it took me awhile when I first heard it.
- SilasX 10y ago>Actually that is incorrect as there is no guarantee that every prisoner has been in the room at least once over any amount of time. IIRC, in the original statement of the problem, there's also a stipulation that, for all prisoners, the king/chooser/whatever will visit them an infinite number of times (so at any time it must be true that each prisoner will be visited [again or for the first time] if the game doesn't terminate).
- strongai 10y agoAh. I hate these kind of puzzles!
- ggggtez 10y agoOf course a few of these mathematical puzzles assume that the human beings involved are all robotic, and capable of remembering a randomly ordered list 100 long. The blue dot red dot problem being the worst offender because the theorem doesn't hold up of you assume anyone in the village has the wrong internal state.
- deleted 10y ago[deleted]
- amenghra 10y agoA short collection of similar puzzles that have been shared with me over the years: https://quaxio.com/some_math_puzzles/ https://quaxio.com/some_math_puzzles/
- alphaBetaGamma 10y agoA different solution to the Box in box problem, with less math: Consider the square of (length + with + height). The sum of the diagonal terms is the square of the distance between opposite corners, the sum of the off diagonal terms equals half the area of the boxes. We can show that both these terms are smaller for the innermost box. It’s obvious for the diagonal terms, as the opposite corners of a box are the two points of the box that are furthest apart. So the opposite corners of the inner box must be separated by less than the opposite corners of the outer one. For the cross diagonal terms: take axes that are aligned with the inner box. Consider the parts of the outer box that would be projected on the inner box if you projected either on the x&y, x&z, or y&z planes (i.e. you project on the faces of the inner box). These six pieces of the outer box don’t intersect, and each of them is larger than the face of the inner box on which they project. So this part of the outer box has an area bigger than the total are of the inner box. QED
- pkroll 10y agoIt's not in the same vein, but my favorite puzzle is the Monty Hall Problem. Although as is relentlessly pointed out, it's not actually how "Let's Make A Deal" works. Monty Hall shows you three doors, two have goats behind them, one has a brand new car. While still closed, you pick a door. After you've picked, Monty opens one of the other two doors to show you a goat, and asks if you want to stay with your choice, or choose the other remaining door. What do you do? Stay? Switch? Or it doesn't matter? For background and spoiler, https://en.wikipedia.org/wiki/Monty_Hall_problem https://en.wikipedia.org/wiki/Monty_Hall_problem Edit: Spelling
- andrepd 10y agoMonty Hall, not Haul.
- KVFinn 10y agoThe tennis was was so straightforward I was thinking it must be a trick, but it was that simple.
- twhb 10y agoI collect riddles like these! Here are a few of them. Numbered Hats A warden places a hat on the head of each of 100 prisoners, each with a random number from 1 to 100. There may be duplicates. Each prisoner can see everybody's hat but their own. Each prisoner then guesses their own number; if any guess correctly, they all go free. The group may not communicate in any way during the trial, but may strategize beforehand. What strategy has the best chance of success? Colored Hats A warden lines up a group of 30 prisoners so they can see everybody in front of them and nobody behind them, then places either a red or a blue hat on each of their heads, randomly. He then goes from the back of the line to the front, telling each prisoner to guess the color of their own hat. Each who guesses correctly is freed. The prisoners cannot see the color of their own hat, and cannot communicate with each other, but can hear each others' guesses and can strategize beforehand. What strategy saves the greatest number of prisoners? Coins on a Chessboard A warden takes prisoner A into a room containing a chessboard, on each square of which is a coin randomly showing heads or tails. He then indicates a random square on that board. Prisoner A is given the chance to flip one coin (or none), then taken from the room, after which prisoner B is taken into the room and must say which square the warden indicated. The two prisoners may strategize beforehand, but may not communicate during the trial (except with the single coin flip). What should be their strategy?
- iliis 10y agoAh, the Colored Hats is awsome (Haven't tried the other ones, thanks for those)! It gets even more interesting by using three colors instead of two. The solution stays the same in principle, but [guvaxvat zbqhyb guerr vf n ybg yrff boivbhf guna jbexvat jvgu rira naq bqq.] (ROT13) EDIT: Happy now? ;P
- justinpombrio 10y agoEDIT: Yes :-)
- posterboy 10y agoNumbered Hats: Are the guesses secret? Colored Hats: The first one makes a sacrifice and says the color of the next hat. He has a 0.5 chance. The next person thus has a chance of 1. The third has to make a sacrifice again. Naively that is an average 0.75 chance over all. An exact calculation is too complicated for my taste.
- kens 10y agoI like Cheryl's transfinite logic puzzle, which takes logic puzzles to a ridiculous extreme. http://jdh.hamkins.org/transfinite-epistemic-logic-puzzle-challenge/ http://jdh.hamkins.org/transfinite-epistemic-logic-puzzle-ch... The puzzle is inspired by Cantor's transfinite ordinal numbers, which are pretty cool. You don't need to know anything about transfinite numbers to solve the puzzle, but they are interesting in their own right. The simplified idea is suppose you count 1, 2, 3, ... up to infinity (ω). Everyone knows adding 1 to infinity doesn't get you anywhere, but suppose you can do it and get ω+1, ω+2, ... The limit is 2ω. But then you can go 3ω, 4ω, ... Which obviously :-) gets you to ω*ω = ω^2. Then you can keep going with bigger and bigger infinities. See https://en.wikipedia.org/wiki/Ordinal_number https://en.wikipedia.org/wiki/Ordinal_number
- paavokoya 10y agoTitle gore
- gohrt 10y agoSome of these are poorly worded: * Kleptopia is ambiguous about what gets stolen, and what toplogy the boxes/padlocks must have for the solution. * The "clever" solution to Unwanted Expansion isn't a complete proof, unless you add some complicated reasoning or use the non-clever proof, but if you do that, you don't need the "clever" proof at all. * The Wimbledon puzzle doesn't explain the scoring rules of tennis :(
- zem 10y agothe clever solution to "unwanted expansion" only uses the fact that addition and multiplication of two positive integers a, b > 1 always gives an answer that is greater than both a and b, therefore if the expansion never terminates and all your variables are 2, the overall result will be infinite. since expansion doesn't change a result, the pre-expansion evaluation should also be infinite; since it is not, the expansion terminates.