tag:blogger.com,1999:blog-3722233.post8636814725881078416..comments2019-08-25T15:38:35.661-04:00Comments on Computational Complexity: Raymond Smullyan's BirthdayLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-78231794675807380782009-05-29T07:41:23.943-04:002009-05-29T07:41:23.943-04:00I grew up on the puzzle books of Raymond Smullyan-...I grew up on the puzzle books of Raymond Smullyan-- the earliest one (What is the Name of this Book?) is a perfect present for the mathematically inclined 10 or 12 year old-- AND I (with Ray's permission!) borrow many of his puzzles as hw assignments when I teach Discrete Math. <br /><br />For those of you unfamiliar, here's an example of his easiest puzzles (they get much harder-- he even manages to teach all of Godel Incompleteness through puzzles like this one :-) , I forget if this one is from What is the Name of this Book? or from The Lady or the Tiger? but here you go: <br /><br /> When Alice entered the Forest of Forgetfulness, she did not forget everything, only certain things. She often forgot her name, and the one thing she was most likely to forget was the day of the week. Now the Lion and the Unicorn were frequent visitors to the forest. The Lion lies on Mondays, Tuesday, and Wednesdays, and tells the truth the other days of the week; the Unicorn, on the other hand, lies on Thursdays, Fridays and Saturdays, but tells the truth on the other days of the week.<br /><br />One day, Alice met the Lion and the Unicorn resting under a tree. They made the following statements: <br />(1) Yesterday was one of my lying days.<br />(2) Yesterday was one of my lying days too.<br /><br />What day of the week is it? <br /><br />The only "simple" logic puzzle that I like better than the Smullyan ones is Jim Propp's Self Referential Aptitude Test!Lenorehttp://www.cs.tufts.edu/~cowennoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5021416271548434742009-05-25T17:14:02.477-04:002009-05-25T17:14:02.477-04:00"I'll find other stuff to put around the post to m..."I'll find other stuff to put around the post to make it a bit longer"<br /><br />lol :) <br /><br />Happy BirthdayAnonymousnoreply@blogger.com