Wednesday, May 9, 2012

return to the island of liars and truthers

This post has the answers to the puzzles in the last post, so you might want to read that one first.

Jeff left a comment suggesting another question that I wish that I had worked into my little story of the islanders, so this late addition was put in as part 5 which you may have missed if you read the post early. Also there was an error in part 3 which meant that although you could solve the puzzle it didn't really work well, so this was fixed also. Sorry for any remaining errors.

Throughout we are assuming usual two valued logic and the law of the excluded middle, which you either believe or you don't (see here).

I seem to remember being stumped the first time that I came across my first liar and truther puzzle. If you are like me and didn't have the insight of how to solve these the first time, once you see how one is done you will still enjoy applying the same method to figuring out the others.

Before going further you may want to look at the problem in the original post.

1. Going to the Village

You can't just ask the islander what village is up ahead: she might be a liar. Instead you have to find a question whose response will (a) give the answer and (b) not depend on whether the islander is a liar or truther. One possilbe question to ask is "Is that your village?" If the answer is yes, you can rest assured that it is the village of the truthers.
A truther answers "yes" if it is the truther village because they are telling the truth, a liar answers "yes" in the same situation because they are lying. A truther answers "no" if it is the liar village because that's the truth, and again the liar would answer "no" because they are lying. Nice, eh?

2. A Bunch of Islanders

This is probably the easiest of the questions, and there are a variety of ways to figure it out. I think the clearest way to see the solutions is to make a truth table, although presenting it this way is probably more work. Our table will have columns A, B, and C representing Alice, Bob, and Carol, but it will also have columns for the statements that Alice (A), Bob (B) and Carol (C) make about each other. Whether A, B, or C is T (truther) or F (liar) must be consistent with the statements made. For example, when Alice says "Bob is a liar" either A=T and B=F or A=F and B=T. Put another way:

Regardless of who the liars and truthers are, they have to be able to make the statements that they make. So, we know we've found a possible solution when all the columns in the truth table that represent these statements are true.

From the table, the only solutions are that either that Bob is a truther and Alice and Carol are liars, or that Bob is the liar and Alice and Carol are truthers.

3. Looking for the Ferry

Now, in my original post I messed up the wording of the puzzle a bit. I have changed it so you might want to check back. You can answer the puzzle in its original wording using the same method as part 5 (below). The change is that Xavier and Yvette are from different villages and don't want to talk about them, and this change in wording forces you to use a different approach.

In the spirit of the first puzzle, you need to implicate the islanders in the question, so that when the liar is lying then this is somehow conjuncted with their answer (negating their false answer). One way of doing this is to ask Xavier "Which way would Yvette tell me to take to get to the ferry?" Whatever Xavier answers, take the other path.

If X is a truther and Y is a liar, X will truthfully reply with what Y would tell you, which would be a lie. If X is a liar and Y is a truther, then X will lie and tell you the path that Y would not have chosen for you.

4. Leaving the Island

Isaac and Jane are giving you a two statement version of the liar paradox. If they are from the island, this can't be resolved (if I then not J, but then not I, etc.). So, these two must be from off the island, and when Isaac says "Jane is a liar" he doesn't mean "Jane is someone whose every statement is false" but rather means something along the lines "Jane sometimes lies" or maybe "don't trust Jane." In any case, probably best not to hang out with these two and instead spend more time with the islanders who are at least consistent.

5. Postscript: on the Ferry
So, how can you always get the right answer out of an islander? You can generalize the method used in question 1 about the village (unless, as in the reformulated question 3 the islander refuses to talk about their village).

Suppose you want to know if a statement A is true or false. You should ask the islander "would someone from your village say that A is true?" If the answer is yes, then you know, no matter whether the islander is a liar or a truther that A is true, but if they answer no, you know that A must be false. This relies on the double negation that will happen when a liar talks about their village. 

So, you could ask the captain a question like "would someone from your village say that this is the ferry to the mainland?"