The Straight Dope

Go Back   Straight Dope Message Board > Main > General Questions

Reply
 
Thread Tools Display Modes
  #1  
Old 05-07-2007, 06:02 AM
H3Knuckles H3Knuckles is offline
Guest
 
Join Date: Mar 2000
Logic puzzle: ID the Liar and the Truth-Teller

Um, first off, I think this is the right forum for this. If not, please move it.

Okay, I'm sure everyone here is familiar with this one, right? One person always tells the truth, and the other always lies, and you have to figure out which is which. Now, for the purposes of this thread we're assuming that they're people and not talking door knockers (as in the film Labrynth) or anything like that.

Anyway, I'd like to discuss a solution I came up with to solve it with 2 or 3 questions. I figured SDMB's going to have a lot of people who are experienced with this sort of puzzle. I was re-reading the archives of 8-Bit Theater over the weekend and a side reference to this puzzle inspired my solution.

Here goes:
SPOILER:
Pick one person, call them A & the other B. Ask the following questions.
A: At his last meal, what did B have for the main course?
B: At your last meal, what didn't you have for the main course?

If the answers differ, then A is the liar and B the truth-teller (if A were the truth-teller, B would only be able to name the one thing he did have in order to lie, so they'd have to be the same answer).

If the answers are the same, then ask the following;
B: At your last meal, what (if anything) else didn't you have for the main course?

If B answers nothing, he is the liar (He couldn't have had every possible food, so he must have not eaten something else). If B names even one other food, then he is the truth-teller (the liar can't dishonestly say he didn't eat something if he actually didn't eat it).


Got that? Please feel free to tear my theory apart, or point out a blindingly obvious way to do this (I know this is an old riddle, and so there's probably already been a very straight-forward solution).
__________________
"GTA Made Me Do It! It's a training manual for mayhem, and it's in the hands of our youth. When will parents be brave enough to shift the blame to people who have nothing to do with the upbringing of their children? Now, that's when." -Brian Clevinger

Last edited by H3Knuckles; 05-07-2007 at 06:02 AM..
Reply With Quote
Advertisements  
  #2  
Old 05-07-2007, 06:20 AM
Noone Special Noone Special is offline
Guest
 
Join Date: Jun 2003
Not answering your question, but related -- given he same A and B, one of whom always lies and the other always tells the truth: how do you determine, with a single question, the correct answer to a binary (yes/no, right/left...) questions?
SPOILER:
Ask A: "What would B say if I asked him whether it is safe to cross this bridge?" You are guaranteed to get the wrong answer -- If A is telling the truth, he will tell you a lie, since that is truthfully what B would say; if A is the liar, then B would tell the truth, and A will lie about it. Which for a binary question is all you need!
Reply With Quote
  #3  
Old 05-07-2007, 07:43 AM
BlackKnight BlackKnight is offline
Guest
 
Join Date: Aug 2000
I've got nothing to add except this wonderful comic related to the topic: http://xkcd.com/c246.html
Reply With Quote
  #4  
Old 05-07-2007, 07:50 AM
Noone Special Noone Special is offline
Guest
 
Join Date: Jun 2003
Quote:
Originally Posted by H3Knuckles
Um, first off, I think this is the right forum for this. If not, please move it.

Okay, I'm sure everyone here is familiar with this one, right? One person always tells the truth, and the other always lies, and you have to figure out which is which. Now, for the purposes of this thread we're assuming that they're people and not talking door knockers (as in the film Labrynth) or anything like that.

... or point out a blindingly obvious way to do this (I know this is an old riddle, and so there's probably already been a very straight-forward solution).
Eh,
SPOILER:
just make sure it's clearly daytime or clearly nighttime, and ask one of them "is it daytime right now?"
Proceed accordingly
Reply With Quote
  #5  
Old 05-07-2007, 08:02 AM
Chief Pedant Chief Pedant is offline
Guest
 
Join Date: Feb 2007
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"

Last edited by Chief Pedant; 05-07-2007 at 08:05 AM..
Reply With Quote
  #6  
Old 05-07-2007, 08:40 AM
Little Nemo Little Nemo is online now
Charter Member
 
Join Date: Dec 1999
Location: Western New York
Posts: 57,344
Quote:
I've got nothing to add except this wonderful comic related to the topic: http://xkcd.com/c246.html
Or this one.
Reply With Quote
  #7  
Old 05-07-2007, 09:03 AM
A.R. Cane A.R. Cane is offline
Guest
 
Join Date: Oct 2005
Location: The great PNW.
Posts: 3,636
Noone Special 's and Chief Pedant's answers would seem to be the most correct since they are based on information given in the explanation of the problem, w/o relying on any outside assumptions.
Reply With Quote
  #8  
Old 05-07-2007, 09:07 AM
chrisk chrisk is offline
Charter Member
 
Join Date: Nov 2003
Location: Southern ontario
Posts: 5,949
I'd ask either one of them...
SPOILER:

Do two and two add up to four?


Which would seem to indicate that Noone Special and I are going down similar paths.
There are innumerable variants on this theme, of course.
SPOILER:

Simply come up a question where the true answer is as obvious and inarguable as possible. Anyone who gives that answer is a truth teller.
Reply With Quote
  #9  
Old 05-07-2007, 09:29 AM
Frylock Frylock is offline
Guest
 
Join Date: Jun 2001
Can't you do it in just one question?

SPOILER:
"If I ask the other guy whether he's the liar, will he say 'yes?'"

If the answer given is "No" then you've asked the truthteller. If the answer given is "yes" then you've asked the liar.

Further explanation: If you were to ask the liar "Are you the liar," he would say "no." If you ask the truthteller whether "the other guy" (i.e. the liar") would say "yes" when asked if he is the liar, then he will answer truthfully: "no." Meanwhile, if you were to ask the truthteller "Are you the liar," he would say "no." If you ask the liar whether "the other guy" (i.e. the truthteller) would say "yes" when asked if he is the liar, then he will answer, untruthfully, "yes."



Or did I miss the point of the OP?

-FrL-

Come to think of it, that's what happened in Labyrinth, isn't it? And the OP mentions that movie. So I must be misunderstanding the point of the OP.
Reply With Quote
  #10  
Old 05-07-2007, 09:34 AM
Frylock Frylock is offline
Guest
 
Join Date: Jun 2001
Regarding the OP's method,

SPOILER:
I think you can do it just by asking one of them first "What didn't you have for a main course," and then again "What else didn't you have for your main course?"

The liar can't answer the second question except by saying "nothing." The truthteller can give any number of different answers.

This makes the assumption that neither one ate every food in the world for their main course. Ideally, solutions to these puzzles don't make use of contentful assumptions like this.


-FrL-
Reply With Quote
  #11  
Old 05-07-2007, 09:39 AM
Frylock Frylock is offline
Guest
 
Join Date: Jun 2001
Quote:
Originally Posted by A.R. Cane
Noone Special 's and Chief Pedant's answers would seem to be the most correct since they are based on information given in the explanation of the problem, w/o relying on any outside assumptions.
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-
Reply With Quote
  #12  
Old 05-07-2007, 09:46 AM
Malacandra Malacandra is online now
Guest
 
Join Date: Jan 2003
If all you want to know is who is the liar, you can do it in one question:
SPOILER:
"What would you say if I asked if you were the liar?" Both characters would say "No", but presumably the liar will mendaciously claim the opposite.


You can apply the same technique to any other one question to which you must know the truthful answer, tho' in this case you won't know if your responder is the liar or not.
SPOILER:
You ask, for instance "What would you say if I asked if it is raining today?". If it is raining, the truth-teller would say "Yes", and he will say so. The liar would say "No", but being at pains to conceal this fact from you he will say "Yes".


All predicated on the supposition that both respondents are flawlessly logical and entirely rules-driven.
Reply With Quote
  #13  
Old 05-07-2007, 09:52 AM
HazelNutCoffee HazelNutCoffee is offline
Guest
 
Join Date: Jan 2005
Quote:
Originally Posted by Little Nemo
Damnit, that's the one I came in here to post!
Reply With Quote
  #14  
Old 05-07-2007, 09:53 AM
Little Nemo Little Nemo is online now
Charter Member
 
Join Date: Dec 1999
Location: Western New York
Posts: 57,344
The problem with most of these solutions is that they assume the ability to ask multiple questions. Given that ability, the problem is trivial as the numerous solutions here indicate.

The classical liar/truth teller problem is:

There's two people: a liar and a truth teller.
They have a factual piece of information you want.
You're only allowed to ask one question.

If you ask a question you know the answer to, you establish trustworthiness but won't get the information. If you ask for the information, you won't know whether or not the answer you get is true. So the puzzle is to figure out a single question that will reveal the unknown information along with the trustworthiness of the speaker.
Reply With Quote
  #15  
Old 05-07-2007, 09:53 AM
A.R. Cane A.R. Cane is offline
Guest
 
Join Date: Oct 2005
Location: The great PNW.
Posts: 3,636
Quote:
Originally Posted by 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-
I was referring to the first post, I didn't see the second one.
Reply With Quote
  #16  
Old 05-07-2007, 10:37 AM
Frylock Frylock is offline
Guest
 
Join Date: Jun 2001
Quote:
Originally Posted by A.R. Cane
I was referring to the first post, I didn't see the second one.
I was referring to the second post, I didn't see the first one.

-FrL-
Reply With Quote
  #17  
Old 05-07-2007, 10:55 AM
Chronos Chronos is offline
Charter Member
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 53,946
Quote:
So the puzzle is to figure out a single question that will reveal the unknown information along with the trustworthiness of the speaker.
There is no such question, unless the thing you want to know is just who's trustworthy. Assuming you ask a yes-no question, you'll get (at most) one bit of information in your answer, but to determine both who's who and the answer to your question, you'd need two bits.

Also, you want to make sure that your question is phrased as a yes-no. For instance, the question "If I were to ask you which path leads to the village, what would you tell me?" is no good. If you happen to ask that question of the liar, he's free to answer "supercalifragilisticexpialidoceous", or "banana", or "mu", since none of those things is what he would tell you (and hence, all of them are lies, in response to the question "what would you tell me?"). To avoid this problem, you could instead ask "If I were to ask you whether the left road leads to the village, what would you say?".
__________________
Time travels in divers paces with divers persons.
--As You Like It, III:ii:328
Reply With Quote
  #18  
Old 05-07-2007, 11:46 AM
TimeWinder TimeWinder is offline
Charter Member
 
Join Date: Jan 2004
Location: Redmond, WA
Posts: 3,275
Quote:
Originally Posted by Chronos
There is no such question, unless the thing you want to know is just who's trustworthy. Assuming you ask a yes-no question, you'll get (at most) one bit of information in your answer, but to determine both who's who and the answer to your question, you'd need two bits.
I've seen it worded such that one bit is enough, something like "There's a village of truth-tellers and a village of liars. At a fork in the road, one member of each village is standing by the road that leads to their village...."

Basically, by determining which village is which, you get which teller is which for free; the bits are not independent.

Usually, though, you're right -- the question is really to determine the factual question, and determining the truth-teller is a red herring to make you "use up" your one bit of information.
Reply With Quote
  #19  
Old 05-07-2007, 11:59 AM
glee glee is offline
Guest
 
Join Date: Aug 1999
On my island, there are three tribes (which all look alike).

One tells only truths; one tells only lies; one varies randomly.

One representative from each tribe is standing in front of a junction of three paths, only one of which leads to the village.
You have one question to get to the village.

[spoiler on] Did you know they are serving free beer in the village? [spoiler off]

Just follow the crowd...
Reply With Quote
  #20  
Old 05-07-2007, 12:42 PM
H3Knuckles H3Knuckles is offline
Guest
 
Join Date: Mar 2000
Ah, see! I figured you'd all come up with better solutions, and you did!

No, Frylock, no. You weren't mistaken at all. I knew Labrynth had a version in it, but couldn't remember how it went. I was just mentioning it to illustrate that I wanted to eliminate the possibility of the two individuals being some sort of mythical or fantastical entities for the purposes of this exercise. And yes, your way is also better.

Heh, I was just feeling clever (what with the little trap I'd formed with my lead-in questions) and wanted to show off what I had thought up, and figured it'd be fun to see what kinds of things SDMB'ers would come up with.

So far I like the "ask one question with a painfully obvious answer" approach the best. It seems highly "portable" (and by that I mean it could probably be adapted to be viable in any iteration of this puzzle).
Reply With Quote
  #21  
Old 05-07-2007, 12:51 PM
Acsenray Acsenray is offline
Charter Member
 
Join Date: Apr 2002
Location: U.S.A.
Posts: 26,339
Quote:
Originally Posted by Chronos
"If I were to ask you which path leads to the village, what would you tell me?" is no good.
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.
Reply With Quote
  #22  
Old 05-07-2007, 01:31 PM
Noone Special Noone Special is offline
Guest
 
Join Date: Jun 2003
Quote:
Originally Posted by 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-
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
Reply With Quote
  #23  
Old 05-07-2007, 02:18 PM
ChrisBooth12 ChrisBooth12 is offline
Guest
 
Join Date: Sep 2005
Hilight for my question

Quote:
You guys are over thinking this. just ask each of them what color the sky is.

Last edited by ChrisBooth12; 05-07-2007 at 02:20 PM..
Reply With Quote
  #24  
Old 05-07-2007, 02:57 PM
Little Nemo Little Nemo is online now
Charter Member
 
Join Date: Dec 1999
Location: Western New York
Posts: 57,344
Quote:
There is no such question, unless the thing you want to know is just who's trustworthy. Assuming you ask a yes-no question, you'll get (at most) one bit of information in your answer, but to determine both who's who and the answer to your question, you'd need two bits.
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:
SPOILER:
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).
Reply With Quote
  #25  
Old 05-07-2007, 03:01 PM
Indistinguishable Indistinguishable is offline
Guest
 
Join Date: Apr 2007
Quote:
Originally Posted by Little Nemo
The solution is:
SPOILER:
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).
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.
SPOILER:
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.

Last edited by Indistinguishable; 05-07-2007 at 03:02 PM..
Reply With Quote
  #26  
Old 05-07-2007, 03:19 PM
Acsenray Acsenray is offline
Charter Member
 
Join Date: Apr 2002
Location: U.S.A.
Posts: 26,339
Quote:
Originally Posted by 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.
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?
Reply With Quote
  #27  
Old 05-07-2007, 03:22 PM
Indistinguishable Indistinguishable is offline
Guest
 
Join Date: Apr 2007
Well, you'd tighten it up a bit. "If I asked you 'Are you a liar?', would you say 'Yes'?"

Last edited by Indistinguishable; 05-07-2007 at 03:22 PM..
Reply With Quote
  #28  
Old 05-07-2007, 03:23 PM
Chronos Chronos is offline
Charter Member
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 53,946
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?"
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.
Reply With Quote
  #29  
Old 05-07-2007, 03:44 PM
Rigamarole Rigamarole is offline
Guest
 
Join Date: Dec 2005
Quote:
Originally Posted by 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"
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.
Reply With Quote
  #30  
Old 05-07-2007, 04:02 PM
Indistinguishable Indistinguishable is offline
Guest
 
Join Date: Apr 2007
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?

Last edited by Indistinguishable; 05-07-2007 at 04:05 PM..
Reply With Quote
  #31  
Old 05-07-2007, 04:05 PM
Acsenray Acsenray is offline
Charter Member
 
Join Date: Apr 2002
Location: U.S.A.
Posts: 26,339
Quote:
Originally Posted by 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
Liar.











Last edited by Acsenray; 05-07-2007 at 04:05 PM..
Reply With Quote
  #32  
Old 05-07-2007, 04:38 PM
Chief Pedant Chief Pedant is offline
Guest
 
Join Date: Feb 2007
Quote:
Originally Posted by 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:
Originally Posted by 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.
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.
Reply With Quote
  #33  
Old 05-07-2007, 04:46 PM
iamthewalrus(:3= iamthewalrus(:3= is offline
Guest
 
Join Date: Jul 2000
Quote:
Originally Posted by 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?
SPOILER:
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.
Reply With Quote
  #34  
Old 05-07-2007, 05:11 PM
wendigo1974 wendigo1974 is offline
Guest
 
Join Date: Mar 2007
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.
Reply With Quote
  #35  
Old 05-07-2007, 05:45 PM
Chronos Chronos is offline
Charter Member
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 53,946
If we're branching out, here, my personal favorite, from William Wu's riddle site:
Quote:
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?
Reply With Quote
  #36  
Old 05-07-2007, 05:54 PM
Frylock Frylock is offline
Guest
 
Join Date: Jun 2001
Quote:
Originally Posted by ChrisBooth12
Hilight for my question
You're "overthinking" ( ) it as well. You need only ask one of them the question.

-FrL-
Reply With Quote
  #37  
Old 05-07-2007, 06:00 PM
Frylock Frylock is offline
Guest
 
Join Date: Jun 2001
Quote:
Originally Posted by 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?
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-
Reply With Quote
  #38  
Old 05-07-2007, 06:08 PM
Indistinguishable Indistinguishable is offline
Guest
 
Join Date: Apr 2007
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:
Originally Posted by iamthewalrus(:3=
SPOILER:
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.
SPOILER:
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:


SPOILER:
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).
Reply With Quote
  #39  
Old 05-07-2007, 06:15 PM
chrisk chrisk is offline
Charter Member
 
Join Date: Nov 2003
Location: Southern ontario
Posts: 5,949
Quote:
Originally Posted by 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?
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

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.
Reply With Quote
  #40  
Old 05-07-2007, 06:18 PM
Indistinguishable Indistinguishable is offline
Guest
 
Join Date: Apr 2007
Quote:
Originally Posted by Chronos
If we're branching out, here, my personal favorite, from William Wu's riddle site:
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?
Reply With Quote
  #41  
Old 05-07-2007, 06:20 PM
Indistinguishable Indistinguishable is offline
Guest
 
Join Date: Apr 2007
Damn you, chrisk! Couldn't you have at least let some of my post remain original?
Reply With Quote
  #42  
Old 05-07-2007, 06:24 PM
Autolycus Autolycus is offline
Member
 
Join Date: Nov 2002
Location: Ainran
Posts: 11,449
Quote:
Originally Posted by chrisk
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

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.
You owe me an aspirin! Although I'm glad we came to the same answer.
Reply With Quote
  #43  
Old 05-07-2007, 06:25 PM
chrisk chrisk is offline
Charter Member
 
Join Date: Nov 2003
Location: Southern ontario
Posts: 5,949
Quote:
Originally Posted by Indistinguishable
Damn you, chrisk! Couldn't you have at least let some of my post remain original?
Well, the spoiler box was something that I didn't do first.
Reply With Quote
  #44  
Old 05-07-2007, 06:39 PM
Indistinguishable Indistinguishable is offline
Guest
 
Join Date: Apr 2007
Quote:
Originally Posted by chrisk
Well, the spoiler box was something that I didn't do first.
And, I realize with glee, pedantry about the ambiguity of the word "one" remains all mine.
Reply With Quote
  #45  
Old 05-07-2007, 06:54 PM
chrisk chrisk is offline
Charter Member
 
Join Date: Nov 2003
Location: Southern ontario
Posts: 5,949
Quote:
Originally Posted by Indistinguishable
SPOILER:

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?
Yeah - this kind of 'reductio ad absurdum' logic only really works when there's some kind of definitive statement about truth or falsity in the puzzle on which you can hang everything else. "If my reasoning isn't correct, then the authority lied to me", in essence, is where you get to with that.

I especially like some of Smullyan's portia puzzle where he makes up bellini and cellini, the vase makers who insist on inscribing true statements or false statements on their creations. Thus, the inscriptions themselves can refer to who made what, and they get out of being directly self-referential that way.

If there's an inconsistency, then it invalidates everything the author of the puzzles is telling you about bellini and cellini.

Last edited by chrisk; 05-07-2007 at 06:56 PM.. Reason: for to fix coding of quote
Reply With Quote
  #46  
Old 05-07-2007, 08:54 PM
Harmonious Discord Harmonious Discord is offline
Guest
 
Join Date: Apr 1999
Don't sweat the chest. Heat both to a roasting temperature for hours, until the python is fully cooked.
Reply With Quote
  #47  
Old 05-08-2007, 12:35 AM
Rigamarole Rigamarole is offline
Guest
 
Join Date: Dec 2005
Quote:
Originally Posted by wendigo1974
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.
Yeah. Job done in one question because you just got your nose hammered into your face.
Reply With Quote
  #48  
Old 05-08-2007, 03:53 AM
Mangetout Mangetout is offline
Charter Member
 
Join Date: May 2001
Location: England (where it rains)
Posts: 50,957
Noone Special nailed it in post #2 - the way these puzzles are usually constructed is such that you not only need to determine which is the liar and which the truth-teller, but you also need, based on that knowledge, to decide which of two ways to go, or which of two boxes to open, etc - one will reward you and the other certainly kill you, and you're only permitted one question.

So it just isn't enough to ask a straightforward question such as 'am I clapping my hands right now?' - because that will at best only identify who is the liar and who the truth-teller - then you have no questions left and you still need to make the crucial decision.
__________________
Cray-con - the bacon-coloured wax crayon!
Reply With Quote
  #49  
Old 05-08-2007, 04:02 AM
Malacandra Malacandra is online now
Guest
 
Join Date: Jan 2003
Quote:
Originally Posted by Chronos
There is no such question, unless the thing you want to know is just who's trustworthy. Assuming you ask a yes-no question, you'll get (at most) one bit of information in your answer, but to determine both who's who and the answer to your question, you'd need two bits.

Also, you want to make sure that your question is phrased as a yes-no. For instance, the question "If I were to ask you which path leads to the village, what would you tell me?" is no good. If you happen to ask that question of the liar, he's free to answer "supercalifragilisticexpialidoceous", or "banana", or "mu", since none of those things is what he would tell you (and hence, all of them are lies, in response to the question "what would you tell me?"). To avoid this problem, you could instead ask "If I were to ask you whether the left road leads to the village, what would you say?".
Same problem, though: even though the reworded question is yes/no, the liar is still free to say "I don't know". So I guess we're reduced to defining "liar" as "someone who says 'yes' when the truthful answer is 'no' and vice versa". Otherwise even the classic ask-one-guard-what-the-other-would-say technique doesn't work; the liar can say "I don't know", and the truth-teller must say "I don't know".
Reply With Quote
  #50  
Old 05-08-2007, 12:05 PM
chrisk chrisk is offline
Charter Member
 
Join Date: Nov 2003
Location: Southern ontario
Posts: 5,949
This reminds me of one of Raymond Smullyan's:

On the island of knights (truth tellers) and knaves (liars), you come upon a small town and find a native on the road just outside of town. You ask him if the Green goose tavern is in this town.

The native fixes you with a frosty stare. "I'm not going to answer that," he replies, and storms off past you, heading out of town.

What information can you deduce from that?

Reply With Quote
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump


All times are GMT -5. The time now is 04:16 AM.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2014, vBulletin Solutions, Inc.

Send questions for Cecil Adams to: cecil@chicagoreader.com

Send comments about this website to: webmaster@straightdope.com

Terms of Use / Privacy Policy

Advertise on the Straight Dope!
(Your direct line to thousands of the smartest, hippest people on the planet, plus a few total dipsticks.)

Publishers - interested in subscribing to the Straight Dope?
Write to: sdsubscriptions@chicagoreader.com.

Copyright 2013 Sun-Times Media, LLC.