29 ms·
Seven Puzzles You Think You Must Not Have Heard Correctly (2006) [pdf]
- hyperpape 8y agoProblem 7 has an even more fiendish counterpart: https://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever https://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever.
- quickthrower2 8y agoTo make it more fiendish, what if the gods / natives don't know about each other's TRUE/FALSE/RANDOM status (but they are excellent logicians, so they can intuit any information from answers to your previous questions).
- qz3 8y agoVery interesting, but incredibly complex. I'm tempted to make a python implementation to play around with for better understanding.
- augbog 8y agoAwesome post! I kind of want to find more of these types of things (solutions to seemingly complex questions). If anyone has recommendations would love to hear
- eindiran 8y agoI was linked to this blog from a post here the other day. It has a lot of these kinds of questions and the solutions. Here is the prisoners problem: http://datagenetics.com/blog/december12014/index.html http://datagenetics.com/blog/december12014/index.html And here is the dots problem: http://datagenetics.com/blog/october22012/index.html http://datagenetics.com/blog/october22012/index.html
- jimmies 8y agoI read quite a bit of books of that kind when I was young. I didn't read in English, but "One hundred thousand whys" - maths in Chinese was a great one, and this [1] in Vietnamese is a great one. They are all old books and some have solutions we can figure out by using a computer, but in general, they are really cool. My personal favorite that has an English translation available, although it's not on Maths is "Physics for entertainment" by Perelman -- you can get it on Amazon right now. It was published 100+ years ago and problems are still relevant now. It discussed questions such as "When you jump out of a train, should you jump forward or backward?" "Who is wetter, a person standing in the rain or a person running in the rain?" I guess basic maths and science hasn't changed that much, or maybe I was reading them when I was young, so I might not have known any better. 1: http://khoia0.com/PDF-Files/80-BAI-TOAN-THONG-MINH_handuc_v2.pdf http://khoia0.com/PDF-Files/80-BAI-TOAN-THONG-MINH_handuc_v2...
- reificator 8y agoLikely posted because problem #1 was recently on the front page: https://news.ycombinator.com/item?id=16984815 https://news.ycombinator.com/item?id=16984815
- deathanatos 8y agoLove in Kleptopia needs to be explained better. The problem can only be solved if you can afix two padlocks onto a box, and I was presuming the lock box had a single, normally shaped padlock eye, which would make such a thing impossible. I find this happens a lot with "thought" problems: I can't solve it (and can often prove that) because the rules of the problem are inadequately explained.
- scrooched_moose 8y agoTo get super pedantic, even if that was the case you could use a lock out tag out type device to still attach two locks. https://www.media-partners.com/upload/i20121017160441/img1.jpg https://www.media-partners.com/upload/i20121017160441/img1.j...
- HanayamaTriplet 8y agoAnother alternative would be to thread a small steel cable with looped ends large enough for two locks through the eye and then lock the loops together.
- keithnz 8y agothe problem is if you introduce new things, then you can solve it like 1. Bolt Cutters 2. Break the box 3. Send the key design via the internet and a link to https://www.youtube.com/watch?v=8M-HYptOMJI https://www.youtube.com/watch?v=8M-HYptOMJI
- oh_sigh 8y agoUnfortunate that they don't show multiple locks in that image.
- matt-attack 8y agoBut they clearly show multiple holes.
- IshKebab 8y ago
- quickthrower2 8y agoI loved this. Some comments. Not really spoilers I hope... For "Unwanted Expansion" the answer is technically correct but I am displeased that it doesn't prove there wont be any infinite loops. Whereas analyzing invariant in the tree should prove that. For Boxes in Boxes it says "But, if we take ε to be huge", but how big is huge, and what if it isn't huge? Seems like something in the proof is being hand waved over. The natives and suicides I enjoyed they really made me go aah!. The irony about the suicides is that the if the people were too dumb to apply the logic, they'd survive.
- Sniffnoy 8y ago"If we take ε to be huge" just means "let's analyze the growth rate as ε goes to infinity". More formally, what's going on is that you have a function which is polynomial in ε and which is always positive; therefore the leading coefficient must be positive, as if it were negative, the polynomial would be eventually negative. The question "what if it isn't huge" makes no sense; we can pick ε, it's not some external given. (Actually, as mentioned, we're not picking it to be one specific value but rather letting it tend to infinity, but that's another matter.)
- quickthrower2 8y agoThanks. Nice explanation. It's been a while (18 years) since I've read maths proofs.
- gowld 8y agoTurn the "suicides" into escaping prisoners, so being smart enough makes them survive.
- gowld 8y agoYes, the solution to "Unwanted Expansion" is simply "because we assume that math works". It's begging the question. If you don't know what he's assuming, you don't know what proofs are "interesting". You could just as well say, "Because it's a finite" expression. "Boxes in Boxes" doesn't really fit the theme. It's a complicated elementary math problem that's hard to solve, but not "tricky" in way that makes it seem impossible.
- Sniffnoy 8y agoThe "boxes in boxes" problem actually turns out to be true in much greater generality, using a different solution: https://math.stackexchange.com/questions/1909085/suppose-a-box-a-is-contained-in-a-box-b-is-the-total-volume-of-the-k-faces-of-a https://math.stackexchange.com/questions/1909085/suppose-a-b...
- agf 8y agoPrevious discussion: https://news.ycombinator.com/item?id=12380879 https://news.ycombinator.com/item?id=12380879 Some additional fun ones in the comments there.
- readams 8y agoThe nice thing about this is that we can use Dot-town as a halting oracle, which can then be used to solve any specific undecidable problem we'd want to solve. Make the machine output a set of dots after running some unknown computation, such as a search for twin primes. The residents will kill themselves depending on the results.
- millstone 8y agoIn the Dot-town suicides, say the stranger says "Alice has a blue dot." Alice then kills herself. Why would the other residents die? I think this satisfies the requirements: there's certainly some number of blue dots for which the statement would be false, namely zero.
- cortesoft 8y agoYeah, I was thinking about if the stranger said something like, “not all the dots are blue.” This is non-trivial by the definition given, and no one would have to kill themselves at all.
- uiri 8y ago"not all the dots are blue" - in the case where there are n people with n-1 blue dots and 1 red dot, the person with the red dot kills themself, and then everyone else kills themselves because they know that the red dot person killed themself because they did not see any red dots.
- cortesoft 8y agoRight, but if there were two red dots the town is fine. In a one red dot town, you could say “there is at least one blue dot”
- gowld 8y agoBy induction and perspective-taking, 1 person dies each time everyone sits and thinks for a while.
- anyfoo 8y agoWould they be fine? So let's say there are two people with red dots, let's name them Ruth and Rudy. Ruth now knows that "not all dots are blue" (which is equivalent to "there is at least one red dot"). She sees Rudy with the red dot: Fine, here's the person with the red dot. But wait a minute, why is Rudy not killing himself? If Rudy is the only person with a red dot, he should have seen only blue dots... however he knows there has to be at least one red dot, so if he only saw blue dots, the red dot must have been him, so he would have killed himself. But he didn't, so that means he has seen at least one red dot, which isn't him, and isn't anybody else Ruth has seen because she only saw blue dots otherwise. Oh no, it must be Ruth with the second red dot!
- deleted 8y ago[deleted]
- zawerf 8y agoWhere can I find more of these? Do you guys recommend this author's books such as https://www.amazon.com/Mathematical-Puzzles-Connoisseurs-Peter-Winkler/dp/1568812019#reader_1568812019 https://www.amazon.com/Mathematical-Puzzles-Connoisseurs-Pet... ? (It's hard to find the right search term for this that doesn't return a lot of non-mathematical brainteasers or stuff aimed at kids)
- ink_13 8y agoWinkler's book looks pretty good, yes. You'd probably also enjoy the works of Martin Gardner, who wrote a recreational mathematics column in Scientific American for 25 years, which has been collected across many volumes.
- rwmj 8y agoI quite like William Poundstone's books. In this case these two are relevant: https://www.amazon.co.uk/How-Would-Move-Mount-Fuji/dp/0316778494/ https://www.amazon.co.uk/How-Would-Move-Mount-Fuji/dp/031677... https://www.amazon.co.uk/Prisoners-Dilemma-Neumann-Theory-Puzzle/dp/038541580X/ https://www.amazon.co.uk/Prisoners-Dilemma-Neumann-Theory-Pu... Edit: These are not puzzle books specifically, but books about puzzles.
- gjm11 8y agoYes, if you liked these you'll probably enjoy Winkler's books. If you're going to get exactly one of them, I suggest the first rather than the second, but both are good.
- maaaats 8y agoBook of Enigmas by Fabrice Mazza has puzzles similar to some of these in the PDF.
- 3131s 8y agoThe logician Raymond Smullyan wrote many books full of logic puzzles, this one being the most well known: https://en.wikipedia.org/wiki/To_Mock_a_Mockingbird https://en.wikipedia.org/wiki/To_Mock_a_Mockingbird
- yay_cloud2 8y agoI would love to watch/hear someone go about solving these problems, just to see their approach and thought patterns.
- chias 8y agoI found the "trick" solution to Unwanted Expansion to be unsatisfying: unless I am mistaken, it assumes that all of the values must be positive integers, which was not stated as being the case.
- mikenew 8y agoSpent quite a while on the Wimbledon problem before giving up and reading the answer. But the answer is wrong, because they don’t play tiebreakers at Wimbledon (or any of the grand slams besides the US Open). Pretty frustrating TBH. Kind of felt the same about the padlocked boxes one too, although at least that one is more just a little ambiguous vs outright wrong.
- arachnids 8y agoThey don't play tiebreakers in the fifth set. All other sets work normally. The answer is correct because it's only talking about the first three sets.
- 3131s 8y agoYeah, but it's so easy! Why is that considered a hard problem? Just because most people are unfamiliar with tiebreakers in tennis?
- tomp 8y agoAnother very counterintuitive (for me) problem: how do you do better that break even in the following game: 'A' chooses two distinct integers, writes them on slips of paper and holds one out in each hand in a fist. You choose a hand and reveal a number. You must then guess whether the other number is higher or lower than the revealed one, winning $1 if you guess right and losing $1 otherwise.
- mulur 8y agoHmm I'm not exactly good with maths (or puzzles for that matter) but here is a blind stab: By break even, I think you mean that the game is played multiple times, as long as necessary. If you are not following a martingale like strategy (edit: you can't anyways, the bets are fixed) and respond randomly (or with full faith that this is your lucky day, doesn't matter really), you are expected to break even with 50% chance. How can we improve and make better than 50%? 'A' chooses two distinct integers each time. They can choose among infinite number of integers. For the first guess, I can't do better than 50% chance but if I start to keep history of the numbers that were picked it feels to me like I can do better than chance if I assume A chooses their distinct integers uniformly random by expecting a uniform distribution. I don't have much ideas about how to judge uniformness in an unbounded set of integers though but maybe something like: if first hand is less than the average of all previous numbers, I'd say "other number is higher", otherwise I'd say "other number is lower". I feel like this would improve my chances to more than 50% in the very long term (at infinite plays perhaps?) but am not able to prove it. If A is not choosing their numbers randomly with a true RNG then I'd play many games at 50% chance then run their choices through a neural network to extract patterns then I'd do better than random for sure.
- sirclueless 8y agoYou can do better than that. You can guarantee there is > 50% chance you win on the first guess.
- Hoagy 8y agoWow, that is very counterintuitive.. I suppose you could set any threshold x, and play so that if the first number is bigger than x you stick, otherwise you switch. This would be strictly better than random (break even) if x is within the range of numbers that A is picking from and the same as random if not. It depends on when you measure your chances: before A has picked a generator this gives you >50% chance but if A has already picked a range to draw from that doesn't contain x then you're back to 50/50. Still, I think this would count as guaranteeing >50%?
- brownbat 8y agoAs to the dots, I enjoyed this variation from xkcd, where I first encountered it: https://xkcd.com/blue_eyes.html https://xkcd.com/blue_eyes.html It massively improved our play at Hanabi: https://boardgamegeek.com/boardgame/98778/hanabi https://boardgamegeek.com/boardgame/98778/hanabi Probably would be a useful puzzle for improving your Spades or Bridge game, or any game you play with a partner with limited information. Also, it gets much worse than The Random Native. George Boolos has a variation called "the hardest logic puzzle ever." It goes like this: “Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language in which the words for ‘yes’ and ‘no’ are ‘da’ and ‘ja’, in some order. You do not know which word means which.” There's an ongoing effort out there to make this variation even harder: https://arxiv.org/abs/1206.1926 https://arxiv.org/abs/1206.1926
- jmblpati 8y agoI think there's an easier to visualize solution to the box problem. Let A have dimensions (a,b,c) and let B have dimensions (x,y,z). Assume A fits inside B. We have (a+b+c)^2 = a^2 + b^2 + c^2 + 2ab + 2ac + 2bc. This is the sum of the A's hypotenuse squared plus its surface area. The same holds for B. Note that A's hypotenuse is at most that of B-- the hypotenuse of a is its longest axis, and it needs to fit in B somehow. Further, note that the surface area of A is less than that of B. To see this, consider the nesting of A inside B and realize that both boxes' interiors are convex sets. Imagine inflating A inside of B by taking the sets A_t consisting of all points within B that are within distance t of a point in A. It is not hard to see that this inflating operation can only increase the surface area of A, and since the maximum surface area we can get is that of B we have that A has smaller surface area than that of B. Thus, (a+b+c)^2 = (A hypotenuse)^2 + (A surface area) <= (B hypotenuse)^2 + (B surface area) = (x+y+z)^2. The claim follows.
- emsy 8y agoHonestly I already lost interest after reading the solution to the first problem, because there's no indication that the prisoners are allowed to alter the boxes in advance. This is such a dumb "gotcha". Edit: I re-read the solution and it doesn't require actual labeling (It's hard to imagine, because I'm not a native English speaker).
- johnc1231 8y agoI always liked the prisoner box question, but I prefer the phrasing where the prisoners are assigned a number and the boxes are numbered. I feel like the "prisoners have to come up with a name to number mapping" step just gets in the way of the interesting part.
- ColinWright 8y agoIf the evil dictator does the naming/numbering then they can guarantee failure. The randomisation of the numbering of the prisoners is important to avoid that.
- CamperBob2 8y agoI don't understand one assertion that the author makes in the solution, though: If it happens that the permutation has no cycles of length greater than 50, this process will work every time and the prisoners will be spared. Obviously that's not true as written, because the first prisoner has odds of 50% no matter what function or algorithm they use to choose the boxes they open. If they fail in their initial guesses, the game stops immediately and everyone dies. What am I missing? Furthermore, if you simplify the case to two prisoners and two boxes, where each is allowed to open one box, the odds of "success" are clearly only 25%. What happens as the number of prisoners and boxes grows that improves the odds? This isn't a classic Monty Hall variation where the participants have additional options as the game progresses -- it's completely predetermined.
- fydorm 8y agoIf it has cycles of 50 or less only, then they're guaranteed to find their own name (they start the cycle on the box corresponding to themselves, so that cycle must contain them). Incidentally, the "first prisoner" might as well be every prisoner, because they aren't allowed to observe each other, communicate, or modify the room.
- CamperBob2 8y agoIf it has cycles of 50 or less only, then they're guaranteed to find their own name (they start the cycle on the box corresponding to themselves, so that cycle must contain them) But there are 100 boxes, assigned at random. The prisoners can come up with a mapping function that predetermines which boxes they will open based on their names, but that function will have no relationship to the one (if any) that was used by the warden. There is no way to guarantee that the first prisoner finds his name, and that seems to be true for all of the others. It must genuinely be a case where I haven't understood the problem correctly.
- teddyh 8y ago“Communicating badly and then acting smug when you're misunderstood is not cleverness.” https://www.xkcd.com/169/ https://www.xkcd.com/169/ I’ve stopped trying to do puzzles. I’ve been misled by bad communication (intentional or otherwise) too many times.
- learnstats2 8y agoThe Dot Town Suicides appears to be incorrect as stated. Suppose there are 100 residents and 2 blue dots. The stranger tells everyone "there are not 98 blue dots" This meets the condition of the question's "non-trivial" but the residents can relax: nobody has learned anything new. The proposed induction is broken, in my opinion.
- Hoagy 8y agoI thought this initially as well: if there are many of each colour, and the only information is that there is at least one blue dot, how could this be new information to trigger the suicides? But this isn't correct. Let's say n = 6, a-c are blue, d-f are red, and the information is that there is at least one blue dot. a knows there are at least two, but thinks b may believe there is only one blue dot. Moreover, a believes b may believe that c may believe that there are no blue dots. So if a was red, the information would mean that b would commit suicide if c did not initially commit suicide, but since neither has happened, a must have a blue dot and therefore must commit suicide. A convoluted process to be sure but does it make sense how the information transmits by ruling out hypotheticals?
- 22c 8y agoThe question is stated correctly, I believe the mix up is in the part about triviality. > “Non-trivial” means here that there is some number of blue dots for which the statement would not have been true. I think this is supposed to say "Trivial means..." If there were 98 blue dots, your statement would not have been true, so it was trivial information. Essentially, if the people of dot town can figure it out themselves, then you've given them a trivial piece of information. They know there aren't 98 blue dots, because they can already see that for themselves.
- chronolitus 8y agoUnless "There are not 98 blue dots" also means "There are not 2 red dots"? Then the process starts and months later all red dots leave. This requires that everyone know only blue or red eyes are allowed.
- JackCh 8y agoThe worst question of the bunch is undoubtedly the tennis question. A very clever alien could answer the other six, but having never been exposed to the rules of tennis would be hopeless against the Wimbledon question. (In fact my knowledge of tennis is poor enough that I don't understand why the question would be considered difficult for somebody who played tennis.)