Logic puzzle: ID the Liar and the Truth-Teller

Factual Questions
21

[QUOTE=Chronos]
“If I were to ask you which path leads to the village, what would you tell me?” is no good.
[/QUOTE]

I think the question you’re supposed to ask is “If I were to ask him which path (left or right) leads to the village, what would he tell me?”

If the path to the village is on the left –

If you’re asking the truthteller, then he will truthfully tell you that the liar will tell you it’s on the right, which you know is the lie.

If you’re asking the liar, then he will lie and tell you that the truthteller will tell you it’s on the right, which you know is the lie.

So, “right” is the lie. “Left” is your answer.

22

[QUOTE=Frylock]
Noone Special’s solution assumes it is possible to tell whether it is day or night. Not a very strong assumption, but an assumption nonetheless.

-FrL-
[/QUOTE]

Then just raise your right hand and ask A “Is my right hand raised?”

The more interesting question however is “how do you determine the correct answer to a yes/no question with one question?” for which see (my) post #2 in the thread as well as Acsenray’s post #21

23

Hilight for my question

[/COLOR]

24

I should have written “the trustworthiness of the answer” rather than “the trustworthiness of the speaker” in my final line. But everything else I wrote is correct.

It’s ridiculously easy to determine whether a person is telling truth or lies. Just ask him any question with a known factual answer and see whether he tells the truth or lie. Where’s the challenge? And if you’ve got more questions you can ask them now, knowing whether your answers will be true or not. The challenge, as I wrote, is trying to get unknown information from one question.

The solution is: Ask either of them how the other would answer a question. If you pick the truth teller, the other guy is the liar, so the truth teller will answer your question with a lie. If you pick the liar, the other guy is the truth teller and he would give you a true answer, so the lair will lie to you by giving you a false anwer to your question. In either event, you know the answer you got was a lie and from there you can figure out the truth (assuming you phrased your question well).

25

[QUOTE=Little Nemo]
The solution is: Ask either of them how the other would answer a question. If you pick the truth teller, the other guy is the liar, so the truth teller will answer your question with a lie. If you pick the liar, the other guy is the truth teller and he would give you a true answer, so the lair will lie to you by giving you a false anwer to your question. In either event, you know the answer you got was a lie and from there you can figure out the truth (assuming you phrased your question well).
[/QUOTE]

Yes, people keep posting this solution, though I don’t know why. As others have pointed out (e.g., Malacanda), you can do it much more directly. Just ask the guy how he himself would answer the question, and he’ll give you the truth, no need for inversion on your part. Hell, this works even if there’s only one guy there.

26

[QUOTE=Indistinguishable]
Yes, people keep posting this solution, though I don’t know why. As others have pointed out (e.g., Malacanda), you can do it much more directly.
[/QUOTE]

Can you see how the liar might answer these questions differently?

A: Are you a liar?

B: If I asked you whether you were a liar, what would you tell me?

27

Well, you’d tighten it up a bit. “If I asked you ‘Are you a liar?’, would you say ‘Yes’?”

28

Same problem as the example I wrote. The truth-teller would not tell you “xyzzy”, so if the liar told you that he would say that, he’d be lying, as he’s required.

29

[QUOTE=Chief Pedant]
Question 1, asked of A: “Is B a liar?”
Question 2, asked of A: “What would you answer if I asked you if B is a liar?”

If the answers are the same, A tells the truth.
If the answers are different, A is a liar.

If you want to assume they do not know if the other is a liar, substitute a question for which the answer is known…e.g. “Are you sitting on a chair…etc”
[/QUOTE]

As Indistinguishable points out, this 2-question system is redundant. In your example, why would you need to ask Question 1 at all? The answer will be yes, whichever one you ask. You only need to ask Question 2.

30

Of course, it’s fairly rare to find dedicated inveterate liars. The more common and devious sort tells the truth sometimes and lies sometimes. Which brings me to one of my favorite puzzles (to slightly hijack this thread):

You stumble across a cave with 16 chests in it. One contains masses of gold, the rest contain flesh-eating bacteria. There’s a guard who knows which chest contains the gold, who has a peculiar condition. He is capable of lying, but only once in his lifetime can he do so.

How many Yes/No questions must you ask him in order to ensure you can get to the right chest, and how would you do so?

31

[QUOTE=Indistinguishable]
Of course, it’s fairly rare to find dedicated inveterate liars. The more common and devious sort tells the truth sometimes and lies sometimes
[/QUOTE]

Liar.

:smiley:

32

[Quote=Chief Pedant]

Question 1, asked of A: “Is B a liar?”
Question 2, asked of A: “What would you answer if I asked you if B is a liar?”

If the answers are the same, A tells the truth.
If the answers are different, A is a liar.

If you want to assume they do not know if the other is a liar, substitute a question for which the answer is known…e.g. “Are you sitting on a chair…etc”
[/Quote]

[QUOTE=Rigamarole]
As Indistinguishable points out, this 2-question system is redundant. In your example, why would you need to ask Question 1 at all? The answer will be yes, whichever one you ask. You only need to ask Question 2.
[/QUOTE]

You are absolutely correct. Mea culpa for being in a hurry.
Ask only question number 2. If the answer is “no” you are talking to the liar.
If it’s “yes” you are speaking to the truth-teller.

33

[QUOTE=Indistinguishable]
Of course, it’s fairly rare to find dedicated inveterate liars. The more common and devious sort tells the truth sometimes and lies sometimes. Which brings me to one of my favorite puzzles (to slightly hijack this thread):

You stumble across a cave with 16 chests in it. One contains masses of gold, the rest contain flesh-eating bacteria. There’s a guard who knows which chest contains the gold, who has a peculiar condition. He is capable of lying, but only once in his lifetime can he do so.

How many Yes/No questions must you ask him in order to ensure you can get to the right chest, and how would you do so?
[/QUOTE]

You can do it in 7, by numbering the boxes with a 7,4 Hamming code and asking questions that give you single bits. I’m sure there’s a simpler way to do it, but I doubt there’s a way to do it in fewer than 7 questions.

34

This may be over simplyfying things:

Two white guys standing in a room, walk up to first guy and ask “Are you negro”

White guy and and a black guy standing in a room, walk up to either and ask “Are you negro”

Job done in one question.

35

If we’re branching out, here, my personal favorite, from William Wu’s riddle site:

36

[QUOTE=ChrisBooth12]
Hilight for my question

[/QUOTE]

You’re “overthinking” ( :rolleyes: ) it as well. You need only ask one of them the question.

-FrL-

37

[QUOTE=acsenray]
Can you see how the liar might answer these questions differently?

A: Are you a liar?

B: If I asked you whether you were a liar, what would you tell me?
[/QUOTE]

I don’t understand your point. The liar can not answer B by saying anything to the effect “I would tell you I am not a liar.” Meanwhile, the truthteller must answer by saying (words to the effect of) “I would tell you I am not a liar.” So the question distinguishes between them.

-FrL-

38

Incidentally, I forgot to make a stipulation that I intended for my problem, that future questions couldn’t be designed to take advantage of the responses to past questions (i.e., I really should have said you write down N questions, then N guards come in and independently answer them, with at most one of the guards lying). So now, I guess, I actually have two different problems for people to tackle.

[QUOTE=iamthewalrus(:3=]

You can do it in 7, by numbering the boxes with a 7,4 Hamming code and asking questions that give you single bits. I’m sure there’s a simpler way to do it, but I doubt there’s a way to do it in fewer than 7 questions.

[/QUOTE]

Precisely correct, exactly the solution I intended; I’m actually somewhat saddened it got answered so fast, but I knew that was a risk here (I’d put a smiley here, but it always seems odd to have a smiley poking out from the spoiler box. [I’d put another smiley here…]) Incidentally, without the stipulation I intended, I can think of some “simpler” (i.e., easier to explain) ways to do it in the same number of questions. As for the simple and elegant proof that your solution is minimal:

Suppose you have a scheme for asking N questions. Then there are (at most) 2^N many possible response series you have to deal with. With each chest, we have to associate (at least) (N+1) many distinct response series: one where there are no lies, one where there’s a lie on the first question, one where there’s a lie on the second question, etc. [The only reason I say “at least” is because, if you allow yourself to ask silly questions like “Have you ever been to Britain?”, there’s some more room for variation]. Since we want to be able to uniquely determine the gold chest from the response series, we need to ensure that no two chests are associate with the same response series. This gives us the constraint that (N+1) * 16 <= 2^N. And, of course, the least N for which that can be satisfied is N = 7 (where it hits it on the button with (7+1)*16 = 2^7 = 128). Q.E.D. (Note that your solution is minimal both with and without the stipulation I forgot to add).

39

[QUOTE=Chronos]
If we’re branching out, here, my personal favorite, from William Wu’s riddle site:
You are an archaeologist that has just unearthed a long-sought pair of ancient treasure chests. One chest is plated with silver, and the other is plated with gold. According to legend, one of the two chests is filled with great treasure, whereas the other chest houses a man-eating python that can rip your head off. Faced with a dilemma, you then notice that there are inscriptions on the chests:

Silver Chest
This chest contains the python.

Gold Chest
One of these two inscriptions is true.

Based on these inscriptions, which chest should you open?
[/QUOTE]

Okay, let’s see. The first thing is that whoever arranged this could have inscribed whatever he or she wanted in each chest, and put whatever they wanted in it. We don’t really have enough clues to figure out what would be ‘fitting’ to them, and so I wouldn’t open either chest - not without being able to shake them each and listen for something slithering inside, figuring out some way of drilling a tiny hole into both and gassing the inside, or something similar :smiley:

But we can figure out what the inscriptions might mean either way. If the python is in the silver chest:
The inscription on the silver chest is true.

The inscription on the gold chest is inherently self-referential, since it is talking indirectly about its own truth. However, in this case, if we take as a premise that the inscription on the gold chest is true, then we reach a contradiction, as then both inscriptions are true, which is not what the gold inscription says.
Alternatively, if we take as a premise that the inscription on the gold chest is false, then we reach a contradiction, as only one inscription is true now, which is exactly what the gold chest affirms.

Thus, if the python is in silver, then the inscription on the gold chest is self-referential in an endlessly contradictory way.

On the other hand, if the python is in the gold chest, then the inscription on the silver chest is false. That means that if we assume that the inscription on the gold chest can either be true or false without contradiction. (True - gold chest only is true. False - both inscriptions are false.) Thus, if the python is in gold, then the inscription on the gold chest is self-referential in a meaningless, but non-contradictory way. The pair of inscriptions are consistent either way it could be interpreted.

So, if we assume that the python is placed in such a way that the inscriptions are consistent, then we should open the gold chest. I wouldn’t bet on that - not after reading about Raymond Smullyan’s Portia N. :smiley:

40

[QUOTE=Chronos]
If we’re branching out, here, my personal favorite, from William Wu’s riddle site:
[/QUOTE]

[spoiler]I’m assuming the “one” on the Gold chest’s inscription is meant to be taken as “exactly one”, rather than “at least one”. (Without that assumption, the problem is hopeless; it could be that both inscriptions are true and the silver chest has the python, or that only the gold inscription is true and the silver chest has the treasure). With that assumption, it cannot be the case that the silver chest’s inscription is true, for then we would have a “truth paradox”, with the gold chest’s inscription being true iff the gold chest’s inscription is not true. Therefore, we know that the silver chest’s inscription is false, and thus the silver chest contains the treasure. [As for the truth value of the gold chest’s inscription, this is still ungrounded, but not inconsistently so. It could be either way].

It is cute, the way you reason from “Well, if things were any other way, we’d have a ‘truth paradox’ on our hands.” However, the troubling problem (and great talking point) is that I could well build a silver and gold chest with those inscriptions and put treasure in the gold one and a python in the silver one. The world, sadly, doesn’t really give a damn about avoiding ‘truth paradoxes’. How crazy is that?[/spoiler]