8 ms·
When Is Cheryl's Birthday?
- ghurtado 11y agoI thought this was a great puzzle when I first saw it. IMHO, it is more satisfying to "think through it" without paper and pencil, since it is relatively simple to resolve. The Python solution proposed is really great, in that it captures both the expressive and functional spirit of the language.
- ternaryoperator 11y ago>since it is relatively simple to solve You are overestimating how simple it is.There are more than 1200 comments on the solution on the NYTimes[1] almost all of them arguing that other dates are correct. [1] http://www.nytimes.com/2015/04/15/science/answer-to-the-singapore-math-problem-cheryl-birthday.html http://www.nytimes.com/2015/04/15/science/answer-to-the-sing...
- Jach 11y agoIt's relatively simple, if you're the kind of person who grasps that 1+1*0 is not 0 under most parsers and under the order of operations implied by e.g. the vector space axioms...
- pdpi 11y ago> under the order of operations implied by e.g. the vector space axioms What, exactly, about vector spaces implies an order of operations?
- Jach 11y agoSee for reference: http://www.math.ucla.edu/~tao/resource/general/121.1.00s/vector_axioms.html http://www.math.ucla.edu/~tao/resource/general/121.1.00s/vec... Addition is only defined on two elements of the space, multiplication is only defined for multiplying an element by a real number, which results in an element. These satisfy the unambiguous distributive axiom, real * (el_1 + el_2) = real * el_1 + real * el_2. Since addition only applies to elements, real * el_1 and real * el_2 must be computed into elements first before the sum. While this doesn't strictly, logically imply the same for real * real + real * real, it's at least suggestive (hence the e.g.) and you can turn to the Peano Arithmetic axioms and definitions of addition and multiplication and do the same thing for natural numbers. Or you can just say the ordering implied by assuming PEMDAS, but just saying that alone is boring and doesn't really expose the elegance in notation/algebraic transformation gained from such a convention. (For those who don't get the reference, every so often some variant of "a + b * 0 + c = ?" will show up in the public's attention and receive very emotional arguments about how it must be 0, or must be a+c, or must be c, or it must be ambiguous and therefore undefined. Similarly to the logic puzzle programmers can just point to the problem expressed in Python for the correct answer...)
- sukilot 11y agoBut even in a vector space these examples are still ambiguous.
- cam_l 11y agoThis comment is, in itself, a description of the issue it raises. Simple is an ambiguous term, and you are using it to describe a different aspect of the problem to the parent (you are both right).
- tiler 11y agoThere are some great examples among the comments of people vehemently defending their provably false beliefs.
- nazri1 11y agoBike shedding, layman version.
- logicallee 11y agobike shedding[1] would be arguing over the names of albert, bernard, and cheryl - wouldn't Alice, Bob, and Carol be more conventional? Or something else that is easier to understand and argue about than the problem itself. so, no, arguing about the actual problem isn't bikeshedding :) [1] http://en.wikipedia.org/wiki/Parkinson%27s_law_of_triviality http://en.wikipedia.org/wiki/Parkinson%27s_law_of_triviality
- InclinedPlane 11y agoIt is a simple logic problem, simpler than the vast majority of logic puzzles. The fact that an enormous number of people in the developed world have poor logical reasoning skills is an entirely separate issue.
- x0054 11y agoI have to admit, it took me more than 5 minutes to figure this one out, so if this was a test problem, I probably failed. Maybe I am not as smart as I think, but it's probably not as simple as people, including other comments to this post, make it out to be. The trick to the problem is pretty obvious right away, but what tripped me is improper perspective. Reading the comments on NY Times, I think this is the same thing that trips up most people as well. After eliminating May and June because they have unique days, which is obvious, I got stuck trying to figure out how Albert would be able to figure out the date after knowing that Bernard now knows the date. So I got stuck on July 16, Aug. 15 and Aug. 17 for a while, because I could not figure out how Albert would know the date if he was told August as the month. It took me a few minutes (ok, like 5 or so, more then I care to admit to my self I suppose :) ) to figure out that my job wasn't to figure out how Albert new, but rather to figure out what the answer was IF Albert now knew the answer. From that it's pretty easy, but it's the perspective that trips most people up.
- deleted 11y ago[deleted]
- lifeisstillgood 11y agoTrust me that is a very eloquent and perceptive explanation of your own failings, and how that applies to others experience. Whatever time limit was arbitrarily set for the "test" you pass the more important test with flying colours.
- vacri 11y agoIt wouldn't have taken you so long if you had've just been doing logic in a classroom. This isn't a puzzle that was sprung on the students by surprise; it was part of their course.
- DannoHung 11y agoThis reminds me of the Blue/Brown eyed villager puzzle. The trick is in figuring out what additional information is actually being added by whatever subsequent statements are being made. It's weird. I usually have a lot of trouble with mathematical word puzzles. Particularly probability. But logic puzzles almost always seem to be pretty easy for me. Now if you want a really fucking hard one, try your hand at this: http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever
- deleted 11y ago[deleted]
- baddox 11y agoIt's very simple in the context of logic puzzles. Similarly, the melody of "Ode to Joy" is very simple to play on the piano. That's not to say that there aren't at least 1,200 people unable to play it on the piano. But it is one of the simplest recognizable melodies to play on the piano, and is likely playable by the vast majority of people with a few months of piano lessons.
- chongli 11y agoThe hard part is not the logic, it's actually figuring out that this is a logic puzzle that needs to be solved by deduction and not a bunch of nonsense with terrible grammar. To borrow your Ode To Joy example, it's like trying to learn to play the piece after the sheet music had been torn and tattered, burned and stained with coffee. Sure, the music is simple once you get past all of the garbage in your way. The original version of the puzzle (in the Singapore Math Olympiad) presented the dates in a sparse table format. This little bit of symbolic communication makes it much clearer that the answerer is supposed to cross off the dates by a process of deduction, making the puzzle simple to solve.
- baddox 11y ago> The hard part is not the logic, it's actually figuring out that this is a logic puzzle that needs to be solved by deduction and not a bunch of nonsense with terrible grammar. I am seeing this claim a lot, but I do not understand it. Why would readers assume that a riddle is a bunch of nonsense, rather than something with an objective answer? > To borrow your Ode To Joy example, it's like trying to learn to play the piece after the sheet music had been torn and tattered, burned and stained with coffee. I don't see the analogy, because I had no trouble understanding the wording of the puzzle. I thought it was extremely clear and precise. To use your analogy, I feel like I'm looking at a pristine professionally-notated piece of sheet music while everyone else is saying it's torn and tattered.
- sukilot 11y agoIf you learned to play piano in a different notation, Western clef note sheet music would be cryptic. Not everyone has learned the same language of expressing precise concepts.
- picardo 11y agoI'd be interested in seeing a solution in Prolog.
- deleted 11y ago[deleted]
- mattbeckman 11y agoFriend of mine wrote a Scala solution: http://www.agileatwork.com/scala-solution-to-cheryls-birthday-problem/ http://www.agileatwork.com/scala-solution-to-cheryls-birthda...
- deleted 11y ago[deleted]
- haddr 11y agostill looking for solution using RDF/OWL logical reasoning... the python solution is neat, but i have a feeling that there are tools that are more native to these kind of problems than general purpose programming language.
- esfandia 11y agoEpistemic logic would probably be the appropriate tool; at least that's what I thought when I first saw the problem. Epistemic logic is the logic of knowledge and belief: you use a modal operator to express the knowledge of an agent about a certain statement. The statement could be expressed in propositional or first-order logic depending on the expressiveness required (but of course there is a complexity trade-off). Translating roughly from the problem statement (x being the variable holding Cheryl's birthday): Not(Know_Albert(x)) and Know_Albert(Not(Know_Bernard(x) etc. Semantically, the possible birthdays correspond to the possible worlds. A reasoner would be able to solve this by process of elimination, somewhat similarly to a constraint-solver. Resources: Wikipedia entry on Epistemic Logic: http://en.wikipedia.org/wiki/Epistemic_modal_logic http://en.wikipedia.org/wiki/Epistemic_modal_logic Fagin, Ronald; Halpern, Joseph; Moses, Yoram; Vardi, Moshe (2003). Reasoning about Knowledge: http://www.amazon.com/Reasoning-About-Knowledge-Ronald-Fagin/dp/0262562006 http://www.amazon.com/Reasoning-About-Knowledge-Ronald-Fagin... I haven't read the entire book, but the first couple of chapters give you an idea and some great examples not too different from this puzzle.
- andrewprock 11y agoUnfortunately, there are a number of rather curious, and culturally specific, assumptions one must make about the problem. The real puzzles are: 1. "Why did Albert speak first?" 2. "Why did he speak in such cryptic language?"
- anigbrowl 11y agoThese are actually valid questions and you shouldn't be downvoted. The standard interpretation of the problem is highly questionable; Albert's initial remark is not actually dispositive to Bernhard, because if Bernhard had the 19 May date he would know the correct answer immediately without needing Albert to say anything. The suggestion that Albert's first statement necessarily eliminates all dates in May is false, and the answer is indeterminable, as can be readily verified with a Venn diagram. It took me some time to spot the flaw in the problem construction; I initially found the official solution persuasive, but when you think more carefully about it you realize it's actually wholly illogical.
- kleer001 11y agoAlong the lines of the "Bob uses cigarette butts to make new cigarettes. Bob needs 5 cigarette butts to make one new cig. If Bob starts with 25 butts how many cigs can he make?"
- logicallee 11y agocan you make your whole comment more explicit, I don't follow your objection.
- andrewprock 11y agoLet's consider the question: 1. "Why did Albert speak first?" Before we answer this, we need to develop a set of assumptions to operate under. Given the synthetic nature of the problem, we might assume that both Albert and Bernard are of equal ability, and able to make logical inferences based on reasonable assumptions. We'll also assume that both Albert and Bernard are only going to announce the binary state of each others certainty of the answer. Lastly, we'll assume that whoever can deduce the binary state of certainty first, will speak first. These assumptions, while a bit presumptuous, seem on the surface to adhere to the spirit of the puzzle. Given those assumptions, what does it mean when Albert speaks first? It means that he's figured out the binary state of certainty before Bernard. How could that be? If Bernard has the dates 18 or 19, then he knows that he knows, and he also knows that Albert does not know. If Bernard has any other date, he'll know that they both don't know. How does Bernard make this determination? He checks if his date is repeated anywhere. Compare that to the logic that Albert must perform to rule out Bernard's certainty. He must check that all of the dates in his month are in fact repeated. If they both perform these mental operations at the same speed, then Bernard should speak first in the case where he knows a unique date. The only reason why Bernard might not speak first is that he must also reason through whether or not Albert might know the date at this point. If Bernard holds an unrepeated date, the complexity of reasoning through Alberts situation boils down to considering only one month. But if Bernard holds a repeated date, he must consider Albert's situation for two months. So, there exists a time past which Albert must know that Bernard is considering the more difficult situation, and thus he can infer that Bernard does not know. If one assumes precise knowledge of the timing of logical operations, one can make even stronger inferences. To the point of even solving the entire problem without anyone every saying anything, for specific birthdays. I will be the first to admit that this line of reasoning may require certain assumptions which are strained. Thus the question may still remain: 1. "Why did Albert speak first?" Does anyone have a different set of logical assumptions which leads to Albert speaking first? ---- What this exposes really, is the more subtle assumption that the "correct" solution makes: "There is only one way to make inferences in this puzzle." The truth of that statement depends very much on the assumptions one makes about the puzzle. Most problematic is that most assumptions which makes that true, make it impossible for Albert to be the first speaker. It's a kind of logical paradox brought on by the fact that synthetic logic problems do not map very well to real world situations.
- john_butts 11y ago1. HN comment about some aspect of fizzbuzz or whatever. Not how to solve fizzbuzz or whatever; rather, some insight into how people solve problems, which is the interesting part of the question. 2. Two dozen oblivious nerds tell u how to do it in 20 characters of perl
- Gigablah 11y agoAre you offended that people are sharing their knowledge?
- zaroth 11y agoMy own contribution from last week: https://news.ycombinator.com/item?id=9398638 https://news.ycombinator.com/item?id=9398638 http://opine.me/discovering-a-new-fizzbuzz/ http://opine.me/discovering-a-new-fizzbuzz/
- gkoberger 11y agoMaybe I'm missing something, but the "hard" part of this problem is figuring on the trick. Once you know that, it becomes relatively easy – and you can't use a program to figure out the trick.
- jrpt 11y agoThe problem isn't difficult without programming. It's the programming that's elegant because it's an interesting way to solve the program, by expressing their statements as functions and using the know and tell functions. It's actually really great how the logic was translated in code, almost like a direct translation from English to Python. Now that I know how to write the program, if the puzzle were to get rapidly more complex, say with 20 different statements of moderate complexity, I feel confident I could solve it with a program whereas I might struggle with pencil and paper.
- logicallee 11y agoI don't know, can code like this reason about knowledge-about-knowledge in general? For example, can a version of the code be used to solve the 'hardest puzzle' - https://xkcd.com/blue_eyes.html https://xkcd.com/blue_eyes.html (solution: https://xkcd.com/solution.html https://xkcd.com/solution.html) ?
- vacri 11y agoI find the problems with puzzles like these is not the rules, but the ridiculously contrived situations. Why do these entities that function like inert logic gates have to be human? It means that the question has to have silly rule placed on silly rule in order to keep the contrived situation afloat. It means I end up thinking of ways for the mute, inert people to free themselves from the island (who is feeding them? Are there trees to build a raft? etc), rather than 'play by the rules'.
- anon4 11y agoSentient immortal mute beings of pure logic that do not possess the capability of traversing the ocean are people too! I get your point. Still, it's hard to define the puzzle in terms of not-people. Maybe you could call them intelligent robots -- people might find it easier to picture mute robots with hats.
- _asummers 11y agoWhere can I find more puzzles of this flavor? This generated some fun discussion on my Facebook wall.
- bentcorner 11y agoI don't know where to find a general place of more puzzles like this, but here's one I enjoyed: http://www.xkcd.com/blue_eyes.html http://www.xkcd.com/blue_eyes.html
- n1ghtmare_ 11y agoA lot of similar puzzles: http://puzzling.stackexchange.com/questions?sort=votes http://puzzling.stackexchange.com/questions?sort=votes
- frik 11y agoCould one use Julia instead of Python? "iPython" already supports Haskell and Julia kernels too. A iPython Javascript kernel would also make sense given its popularity and its functional inspired syntax.
- frik 11y agoA downvoter confused "iPython", its a "notebook" based (think Mathematica notebook) command shell for interactive computing in multiple programming languages. They already renamed it to "Jupyter" as "iPython" was very confusing name.
- janhaak 11y agoThis is quite disturbing for me. My Aunt's name is Cheryl. Her husband, Bernard. Guess his brother's name!
- vessenes 11y agoThis is just beautifully expressive python. I wouldn't think of using it this way: writing return (not know(possible_dates) and all(not know(tell(Day(d))) for d in possible_dates)) feels almost zen to me; or at least like Mr. Norvig likes himself some lisp at times.
- logicallee 11y agoPython: write pseudocode, and then make sure it's indented properly.
- selectiveshift 11y agoHe does in fact like himself some lisp: http://norvig.com/paip.html http://norvig.com/paip.html
- kyberias 11y agoCouldn't resist. This is the solution ported to C#: https://github.com/kyberias/cherylsharp https://github.com/kyberias/cherylsharp
- baronofcheese 11y agoFunny you say it. I had a go at it as well. Seems like we ended up more or less the same :) https://gist.github.com/Cheesebaron/f813576f62dce8391c3b https://gist.github.com/Cheesebaron/f813576f62dce8391c3b
- ibejoeb 11y agoHere's my quick solution in modern SQL. This is more expensive than it needs to be, but doing it this way lets you see the truth table by commenting out the final predicate. fiddle: http://sqlfiddle.com/#!15/0c419/160/0 http://sqlfiddle.com/#!15/0c419/160/0 gist: https://gist.github.com/ibejoeb/df57cb34bbe609293d6e https://gist.github.com/ibejoeb/df57cb34bbe609293d6e
- zhte415 11y agoThe problem with this problem, the way it was originally put, was the utterly confusing English masked into a logic problem. Write your specifications clearly, and then it does not become an internationally shared 'problem' to solve. [I work with insanely documented specifications just like this, year after year. Not putting a problem clearly is not something to aspire to.]
- baddox 11y agoWhy do you think that confusion over the English description is more to blame than the difficulties many people face with logic puzzles?
- zhte415 11y agoI do not make a comparison to 'difficulties many people face with logic problems' and did not make an assertion that many people face difficulties with logic puzzles. Getting back to the article: the problem is worded so badly it should be sent back to the author to more coherently express what they think. Specifications, etc...
- chongli 11y agoA lot of people reading it probably didn't even realize that it is a logic puzzle. To those, it may be some kind of obscure riddle with terrible grammar. Heck, it's not even clear that Albert and Bernard are communicating with one another and not merely with the answerer. If you assume they do not communicate at all then the puzzle becomes impossible.
- Fando 11y agoMaybe someone already mentioned this, but this problem is a simplified formulation of a famous number thoery riddle called 'The Sum and Product Riddle' which is even more baffling. Here it is http://blog.computationalcomplexity.org/2007/01/sum-and-product-riddle.html?m=1 http://blog.computationalcomplexity.org/2007/01/sum-and-prod...
- tomp 11y agoFor the more mathematically minded readers, here's a harder version of the problem: http://jdh.hamkins.org/transfinite-epistemic-logic-puzzle-challenge/ http://jdh.hamkins.org/transfinite-epistemic-logic-puzzle-ch...
- xarien 11y agoI'd have gone a different way since my setup and approach was a bit different (I took a more visual approach). While this solution is elegant, it's also incredibly hard to do in the real world as it requires far too much knowledge to properly assign the "correct" definitions. It's no different than having a perfect health heuristic land on your lap. When I did this a while back, my approach was to construct a 5x4 matrix with blanks (5 unique dates x 4 unique months). This allowed the clues to cross off entire rows and or columns until only 1 pair stood standing. Personally, I find the construction of the solution much more interesting than the problem itself given how many people participated.
- Nursie 11y agoIf you're puzzling over this you've done it wrong. There is no inference from silence. There is no humanity in such a question, there is simply the information you're given and the application of logic to narrow down the answers. The Singaporean kids that took the exam knew this and anyone that's ever taken a maths or logic exam should know this. You don't guess what might have happened from human behaviour because you don't know, you don't look for a 'trick' to give away the answer, you simply use the data in the question to narrow down the possibilities until you can arrive at an answer. The moment you think "but what if this action could have taken place because if he knew he would have said" you have failed. And you probably suck at debugging.