Thursday, May 31, 2012

liar-truther accusation graphs

One of the puzzles concerning the island of liars and truthers (#2 in the first post about these problems) involved a bunch of islanders accusing each other of lying, leaving you to sort out who was telling the truth and who wasn't.

I decided to present the solution in a truth table (in this post), but it turns out that for this kind of puzzle the answer is presented better (and found more easily) if you use a graph. For example, the graph at the top of the page (K_24,12) could represent 24 truthers, each accusing a group of 12 liars of lying - or it might be 12 truthers and 24 liars - it's hard to tell :).

Let's say you have an "accusation" puzzle, where a bunch of islanders are directly accusing each other of lying. Let each islander be represented by a vertex, and let each accusation be represented by an edge.

Note that it amounts to the the same thing if A accuses B, B accuses A, or if they both accuse each other, so it doesn't matter who accuses who - our graph doesn't need to have directed edges. The important thing to note is that if there is an accusation between A and B, then one of them must be a liar and the other must be a truther.

We want to find out who among the islanders are liars are truthers, and maybe represent this by colouring the vertices for liars one colour, and the vertices for truthers another colour. If A and B are connected by an edge this means that one of them is accusing the other of being a liar, they can't both be liars or both be truthers - so the vertices cannot be the same colour. You may see where this is going:  finding a solution to the puzzle is equivalent to finding a two-colouring of the graph.

What if in our puzzle we have some islanders "praising" other islanders - like if D says "A is telling the truth."? We might be tempted to add in a new kind of edge to represent this in our graph, but this isn't necessary. If D says that A is telling the truth, this means that both D and A must be the same - they must either both be liars or both be truthers. From the point of view of our graph, we can represent this by collapsing D and A and represent them both by the same vertex. Note that you can't have D and A accusing each other and praising each other at the same time - you get a liar paradox if you do.

Here is an example:

You meet a group of 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." At that moment, Dave walks up and says "Alice is telling the truth." Who are the liars and who are the truthers?

We can start by modeling the problem as a graph - with edges for "accusations" and to start with the "praise" as a dashed edge (1). Then we collapse the nodes that have a dashed edge between them (2) and finally find a 2-colouring of the graph (3).

This shows that either (a) Alice, Dave, and Carol are truthers and Bob is a liar or (b) Alice, Dave, and Carol are liars and Bob is a truther.

I think that seeing this as a coloring problem makes it more obvious what the solutions will generally look like. For example, if the puzzle hasn't "pinned" any of the islanders by saying explicitly that they are a liar or a truther, or hasn't fixed the number of liars or truthers (e.g. by saying "there are two liars" or something similar) any solution that you find will also give a "complementary" solution by reversing the colours - turning every liar into a truther and vice-versa. Also, in any puzzle where there is an accusation, the group of islanders cannot be all liars or all truthers.

In a problem like that doesn't have any islanders standing alone (i.e. not praising or accusing anyone and not being praised or accused by anyone else), if there is a solution, the graph will be bipartite. The picture at the top of this post is of a complete bipartite graph, which is what you get if all truthers are accusing all liars (or vice-versa). Here are some pictures of complete bipartite graphs, and here are some more.

A lot of liar-truther problems are not like these "accusation" scenarios. See here for more variations on the liar-truther theme.

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?"

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 


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.