Monday, May 7, 2012

on the island of liars and truthers


I've been looking at logic puzzles over the last couple of days - my favorites are the ones that involve the Island of Liars and Truthers.  These logic puzzles are particularly appealing because they can be thought of as variations and elaborations of the famous liar paradox, known and loved by all.

I've come across these in various places - there are quite a few examples of these on the Internet, but if you just google "liars and truthers" you get lots of hits pertaining to conspiracies, so you have to go one further and google "liars and truthers logic puzzle" or "island of liars and truthers" to find them. I didn't find the ones below in my recent searches (although you might find them ... I didn't search too hard, after getting caught up reading about the melting point of steel, etc.) - they are adapted by memory from other sources that I can't recall - they are not original and variations on them are probably pretty common.

The Island of Liars and Truthers 

Preamble

Imagine that you are visiting an island on which there are only two kinds of people (other than yourself): truthers, who always tell the truth, and liars, who always lie. There are two villages - one where all the truthers live, and another where all the liars live. Although they live in separate villages, liars and truthers frequently roam about the island together and generally get along just fine. Talking to islanders is a bit difficult because they all observe the peculiar custom of not answering more than one question in a conversation and generally don't elaborate on any statements they make. Another interesting feature of these islanders is that although outsiders can't distinguish between truthers and liars by how they look, liars and truthers can always tell each other apart.

1. Going to the Village

You are on the island and see a village on the road ahead of you, and you are not sure whether it is the truther village or the liar village. An islander, who may be a liar or a truther, is standing on the side of the road. What one question do you ask her to find out if the village is the truther village or the liar village?

2. A Bunch of Islanders

Leaving the village, you meet a group of three islanders and want to know whether they are liars or truthers. Alice says "Bob is a liar", Bob says "Carol is a liar" and Carol says "Bob is lying." After that, they don't say anything else. Suppose the group consists of one truther and two liars - who's the truther? Now suppose that the group consists of two truthers and one liar - who would the truthers be? Can this group be all truthers or all liars?

3. Looking for the Ferry

You've decided to leave the island and are trying to find the ferry that will take you back to the mainland. There is a fork in the road that splits off in two directions. Two islanders, Xavier and Yvette, are standing at the fork. Xavier and Yvette are from different villages; you don't know who is from the truther village and who is from the liar village, and Xavier and Yvette won't answer questions about their villages. What question do you ask one of them to find out how to get to the ferry?

4. Leaving the Island

At the ferry you meet Isaac and Jane. Isaac and Jane are either both from the island, or else have both just come off the ferry from the mainland. Isaac says "Jane is a liar" and Jane responds "Isaac is telling the truth." Are Isaac and Jane from the island?

5. Postscript: on the Ferry

It's a slow day, and you are the only passenger on the Ferry: it is just you and the captain. As it pulls out into the harbour you realize that you might have boarded the wrong ferry - is this really the boat that is going to the mainland? You can ask the captain, an islander himself, one question to find out.

Update: some answers here, and some discussion about drawing graphs for problems like #2 here.