Liars and Their Motivation
You arrive at an archipelago of many islands. On each island there are two villages. In one village truth-tellers live, and they always tell the truth. In the other village liars live, and they always lie. The islanders all know each other.
On the first island you stumbled upon three islanders and you ask each of them your question:
How many truth-tellers are there among you?
Here are their answers:
A: One.
B: A is wrong.
C: A and B are from the same village.
Can you determine who is a truth-teller and who is a liar?
This island is called a classic island, where all behave as if they were in a standard logic puzzle. It is a perfectly nice puzzle but B and C didn’t answer the question: B ratted on A, and C went on a tangent. When I was younger, I never cared about the motivations of A, B, or C. Their answers are enough to solve the puzzle. But now that I am older, I keep wondering why they would choose these particular answers over other answers. So I invented other islands to impose rules on how the villagers are allowed to answer questions.
Now you travel to the next island that is called a straightforward island, where everyone answers your question exactly. You are in the same situation, and ask the same question, with the following result:
A: One.
B: One.
C: Ten.
Can you determine who is a truth-teller and who is a liar?
Once again we wonder about their motivation. This time C told an obvious lie, an answer that is impossible. Why on earth did he say 10? Isn’t the goal of lying to deceive and confuse people? There is nothing confusing in the answer “ten.”
Now you come to the third island, which is a straightforward inconspicuous island. To answer your question, a liar wouldn’t tell you an obvious lie. For this particular situation, the liar has to choose one of the four answers that are theoretically possible: zero, one, two, or three. You are again in the same situation of asking three people how many truth-tellers are among them, and these are the answers:
A: Two.
B: Zero.
C: One.
Can you determine who is a truth-teller and who is a liar?
When you think about it, a truth-teller cannot answer zero to this question. So although zero is a theoretically possible answer, we can deduce that the person who said it is a liar. If liars are trying to confuse a stranger, and they’re smart, they shouldn’t answer “zero.”
The next island is a straightforward inconspicuous smart island. The liars on this island are smart enough not to answer zero. You are in the same situation again and ask the same question with the following outcome:
A: Two.
B: Two.
C: One.
Can you determine who is a truth-teller and who is a liar? You shouldn’t be able to. There are three possibilities. There are two truth-tellers (A and B), one truth-teller (C), or zero truth-tellers.
Let us assign probabilities to liars’ answers. Assume that liars pick their answers randomly from the subset of wrong answers out of the set: one, two, three. If two of these answers are incorrect, they pick a wrong answer with probability one half. If all three of the answers are incorrect, they pick one of them with probability one-third. Suppose the people you meet are picked at random. Suppose that the probability that a random person is a truth-teller is 1/2. Given the answers above, what is more probable: that there are two truth-tellers, one truth-teller, or zero truth-tellers?
Share:
ablmf:
The two truth-tellers case. The more liar you have, the less likely that you get a particular answer combination.
17 February 2014, 4:17 pmpeter:
Here are other possible questions:
1) Are there answer sets which are impossible (do not admit a solution)? Find all of them.
2) Describe answer sets which lead to the same answer.
19 February 2014, 2:57 ampeter:
More possible developments:
19 February 2014, 8:02 am1) go to an island where inhabitants try to make the life of the interviewer as hard as possible – a) interviewees can group themselves as they wish, b) (independent feature) define if answers can be thought as a set or a sequence, for example, if C is the last to speak and is a liar then he/she speaks a text which makes the solution of the interview problem as hard as posssible or even impossible.
2) Try to find complexity measures of solutions for different cases and classify answer sets.
Tanya Khovanova:
peter,
I was planning to move in the directions you are suggesting.
23 February 2014, 12:18 pmHector:
You totally stole the idea for this post from me! I published mine two months before. What do you have to say for yourself?!
26 March 2014, 5:25 amhttps://hexxponies.wirehound.com/blog/2013/12/24/knights-knaves/
Tanya Khovanova:
Hector,
There is no overlap between your post and my post.
26 March 2014, 10:38 amJosh Lanyadoo:
Oops, ignore my last post. This is correct:
“If all three of the answers are incorrect, they pick one of them with probability one-third.”
Aren’t there more lies that they would be smart enough not to tell, though? Out of the possible 10 combinations
A:1 B:2 C:3 = must be 0 or 1
A:1 B:3 C:3 = must be 0 or 1
A:2 B:2 C:3 = must be 0 or 2
A:3 B:3 C:3 = must be 0 or 3
A:2 B:2 C:1 = 0,1 or 2
A:3 B:3 C:2 = must be zero
A:3 B:1 C:1 = must be zero
A:2 B:2 C:2 = must be zero
A:2 B:1 C:1 = must be zero
A:1 B:1 C:1 = must be zero
half will never be said by smart liars, so given A:2 B:2 C:1, depending on if there are really 0, 1, 2 or 3 there will be 4 different odds for their choice.
If there are 0, the odds they picked A:2 B:2 C:1 would be 1/5.
If there are 1, the odds they picked A:2 B:2 C:1 would be 1/3.
If there are 2, the odds they picked A:2 B:2 C:1 would be 1/2.
If there are 3, the odds they picked A:2 B:2 C:1 would be 0.
(I wonder what that would look like at 4 or 5 villagers, or if you asked “How many liars among you?”)
Given that the odds of meeting a truthteller are 1/2, the odds of meeting 0 is 1/8, 1 is 3/8, and 2 is 3/8(and 3 is also 1/8, but we know it’s not 3 for A:2 B:2 C:1).
From there, you can figure out the odds of having both met the necessary number of truthtellers and the remaining liars having constructed A:2 B:2 C:1
The odds you get A:2 B:2 C:1 after meeting 0 is 1/40, the odds you get it after meeting 1 is 1/8, and the odds you get it after meeting 2 is 3/16. Your guess is about 18.06% better than before asking. The odds went from the same that there are 1 or 2(3/8), to 50% more that there are 2 than the next best guess, 1 ((so 15/27 there are 2, 10/27 there are 1, and 2/27 there are 0)). A:2 B:2 C:3 is 7.5 times more likely to be 2 than 0, and the remaining combinations that allow for 1 are 5 times more like to be 1 than 0(same as the relationships for A:2 B:2 C:1). A:3 B:3 C:3 actually gives you the least information, giving you even odds on 0 or 3.
At least I think that’s the solution… Does the order they speak at/you met them matter? I’m not even sure it would change the math too much if it did matter,(you have to wait to have all the information to think about the problem, and the odds are the same regardless of the order; both meeting and listening are statistically independent. You would only be adding more random less ambiguous lies, making it easier to guess, if anything), but I clearly don’t know set theory, or what the hell I’m talking about. I just gave a presentation on the Monthy Hall Problem in high-school once and play a lot of poker… Sorry for all the scrolling…
11 April 2014, 3:36 am