hollis@ucf-cs.UUCP (William ) (11/07/84)
[[]] You are shipwrecked and wash ashore onto an island populated by cannibals. There are two types of cannibals on this island: short ones who always tell the truth and tall ones who always lie. As you crawl up the beach, one of the short ones, the chief, approaches you and makes you an offer you can't refuse. The chief blindfolds you and places three men from his tribe near you on the beach. From what they say to you, you must tell the chief which are short and which are tall - and prove your answer. If you manage to do this, you will be set free. Otherwise, you are invited to dinner. As the first tribesman begins to speak, a wave breaks on the nearby reef and drowns out his voice. Then you hear the second say 'The first one said he is short and he is, and so am I". The third one says 'The second one is lying, he is tall and I am short'. You have all the information I had... and I lived to tell about it. Ken Hollis
grady@ucbvax.ARPA (Steven Grady) (11/10/84)
This problem, although a classic, is not the best version of this type of problem. A book which I highly recommend is "What is the Name of this Book (the Riddle of Dracula and other mysteries)" by Raymond Smullyan. Basically, the book consists of about 200 of these kinds (liars, truth-tellers, etc.) of problems, along with other assorted stories and problems involving logic. An example from near the end of the book, which shows some of the more interesting aspects of thios type of puzzle is (I paraphrase): You're in Transylvania. There are two types of people, humans and vampires. Humans always say what they believe, and vampires always say the opposite of what they believe. To make things interesting, there both sane and insane people. Thus there are sane humans, insane humans, sane vampires, and insane vampires. A moments thought wil show that in most circumstances only sane humans and insane vampires will speak the truth. But consider, if a Transylvanian says "I believe X", can you determine whether X is true? Can you determine anything about the speaker? Note: this is not the hardest type of problem. One also gets into "Elite" Transylvanians, who use the words "bal" and "da" for yes and no, not necessarily repectively. Also included is an understandable explanation of Godel's theorem, and various stories, aneccdotes, jokes to entertain when your mind is not working at it's best. -Steven Grady