Logic!
There’s a classic setting for logic puzzles that goes like this:
On a remote tropical island, the natives are divided into two types. The first type always tell the truth and the second type always lie. (Sometimes there’s also a third type who lie only some of the time.) Generally you ask them yes-or-no-questions, but sometime they volunteer information from which you can draw conclusions from.
The fun of this is that the puzzles can be easy, ridiculously complex, or anything in between, but the reasoning is straightforward enough for the solutions to be clear. Let’s start out with some simple ones.
If you ask a native whether he’s a truth-teller:
- A truth-teller will truthfully say yes.
- A liar will falsely say yes.
So it’s a useless question. Suppose, on the other hand, you ask one native (call him Bill) whether another one (Chuck) is a truth-teller.
- If both are truth-tellers, the answer is yes.
- If Bill is a truth-teller and Chuck is a liar, the answer is no.
- If Bill is a liar and Chuck is a truth-teller, the answer is a lying no.
- If both are liars, the answer is a lying yes.
So the question that actually got answered is not what you asked; it’s “Are you and Chuck the same type?” Suppose that you had asked that.
- If both are truth-tellers, the answer is yes.
- If Bill is a truth-teller and Chuck is a liar, the answer is no.
- If Bill is a liar and Chuck is a truth-teller, the answer is a lying yes.
- If both are liars, the answer is a lying no.
So the question that got answered this time is “Is Chuck a truth-teller?”
Can we find a question that will be answered in the affirmative only by truth-tellers? One answer is to simplify the above by making Bill and Chuck the same person, i.e. “Are you the same type as yourself?” (This is of course an instance of “Is incontrovertible fact A true?”, which is in general cheating, since it’s too easy.) Another is to go meta and ask “Are you the type who would say that you’re a truth-teller?” A liar would, if asked, say that he was a truth-teller, so he’d lie to the meta-question and say no.
Suppose Bill says that he and Chuck are both truth-tellers.
- Bill could say this if they both really are truth-tellers.
- If Bill is a truth-teller and Chuck is a liar, Bill couldn’t say it.
- If Bill is a liar, it’s false, so he could say it no matter what type Chuck is.
So the statement amounts to “Bill being a truth-teller implies that Chuck is also a truth-teller,” using the usual definition of the material conditional, where “P implies Q” is false if and only if P is true and Q is false.
On the other hand, if Bill says that he and Chuck are both liars
- Bill could never say this if he was a truth-teller.
- If Bill is a liar, he could say it only if it’s false, that is, if Chuck is a truth-teller.
So this similar-sounding statement is much more precise and proves exactly what types Bill and Chuck are.
A bit more complicated: what if Bill says “Chuck would say I’m a truth-teller”? There are two issues:
- Would Chuck really say that?
- Based on the answer to 1, would Bill say that Chuck would say that?
- If both are truth-tellers, 1 and 2 are both yeses.
- If Bill is a truth-teller and Chuck is a liar, 1 is a no, as therefore is 2.
- If Bill is a liar and Chuck is a truth-teller, 1 is no, so 2 is a yes.
- If both are liars, 1 is yes and thus 2 is no.
So this is once again equivalent to “Chuck is a truth-teller.”
Even more complicated: Bill says “If you asked me, I would say that Chuck would say I’m a liar.”
There are now three issues:
- Would Chuck really say that?
- Based on the answer to 1, would Bill say that Chuck would say that?
- Based on the answer to 2, would Bill say this about statement?
- If both are truth-tellers, 1, 2, and 3 are all noes.
- If Bill is a truth-teller and Chuck is a liar, 1 is a yes, so therefore 2 and 3 are yeses.
- If Bill is a liar and Chuck is a truth-teller, 1 is yes, so 2 is a no, so 3 is a yes.
- If both are liars, 1 is no and thus 2 is yes and 3 no.
So the statement really proves that Bill and Chuck are not the same type.
Finally, a puzzle: There are three natives, Dick, Earl, and Fred. Your job is to write down two yes-or-no questions, give them both to Dick, and based on his answers determine how many truth-tellers there are among the three. What are the questions? (There is, of course, more than one possible solution. The simplest correct set of questions wins.)
Eh, this comic remains my favourite solution to this logic problem: http://www.giantitp.com/comics/oots0327.htmlReport
Awesome (or not awesome. Depending on which one I am.)Report
Must both questions be decided up front, or can you choose the second question based on the answer to the first?Report
Up front.Report
Dude, where were you when David Bowie was torturing the children of the 80s?Report
Quoted from an old comment of mine:
There is an old logic parable called the Pilgrim to Jerusalem. At a fork in the road stand two brothers: one will always lie and the other will always tell the truth. The Pilgrim may only ask one question of one brother to find his way to Jerusalem. What is the question the Pilgrim must ask?
“Which fork in the road will your brother tell me to take?” is the question. When the questioned brother says “A”, the Pilgrim must take the “B” fork.Report
Actually, no need. Here’s the easy answer:
1. Ner lbh gur fbeg jub jbhyq fnl gung gurer ner na bqq ahzore bs gehgu gryyref?
2. Ner lbh gur fbeg jub jbhyq fnl gung gur ahzore bs gehgu-gryyref vf srjre guna gjb?
V fhfcrpg gung gurer’f na nafjre gung vaibyirf punvavat erfcbafrf. Jbhyq lbh fnl gung Puhpx jbhyq fnl gung Rq jbhyq fnl….Be fbzrguvat yvxr gung.Report
That works, of course. It’s also possible to solve it without meta-questions, which I declare to be more complex than non-meta questions.Report
What is the definition of a meta-question in this context? Does it include questions to one native about what another native might say, or only questions to one native about how he himself might answer a question?Report
No hypotheticals of any sort are required.Report
Obligatory xkcd reference – there are three guards, one who lies, one who tells the truth, and one who stabs people who ask tricky questions.
Also, in Kingdom of Loathing – there are four guards, one who lies, one who tells the truth, one who can’t be counted on to do either, and one who craves the taste of human flesh.Report
The simplest questions I can think of. I think the second one still counts as a meta-question, though.
1) Vf bayl bar bs lbhe sevraqf n yvne?
2) Jbhyq obgu bs lbhe sevraqf fnl lbh’er n yvne?
Vs obgu dhrfgvbaf ner nafjrerq jvgu n ab, gura gurer ner ab yvnef. Vs gur svefg vf nafjrerq lrf naq gur frpbaq ab, gurer’f bar yvne. Vs gur svefg nafjre vf ab naq gur frpbaq vf lrf, gurer ner gjb yvnef, naq vs obgu nafjref ner lrf, gurer ner guerr yvnef.Report
That also works, but again the hypothetical can be eliminated.Report
Okay, how about:
1) Vf bayl bar bs lbhe sevraqf n yvne?
2) Vf rvgure sevraq bs gur fnzr glcr nf lbh?Report
Jura lbh fnl “bayl bar”, qbrf gung zrna “rknpgyl bar”?Report
YesReport
Alan is correct.Report
The real puzzle is whether the questioner is a liar or truth teller.
The most interesting answer that I have read was when the questioner does not ask questions but add untruthful information: Hey! They are serving free beer in the village!Report
Whenever I hear one of those questions, I have to immediately ask:
How do I know _you’re_ telling the truth?
Seriously, this story is about some people who lie, and some tell the truth. All the time.
This seems rather implausibly. Seriously, how would the liars buy food? Or do anything else. And how the hell do you handle Opposite Day?
So, by Occam’s razor, I am forced to assume that it it _you_ who are lying. (Probably not all the time, just this once.) There are no people who tell the truth all the time, there are no people who lie all the time. In fact, there _might not even be any island at all_.Report
More seriously, I always thought it would be funny to do a puzzle of this form:
You come across a fork in the road with a sign saying ‘One person here lies, and the other tells the truth. You may ask exactly one of them one question, and that is all.’
And, sure enough, two people stand there. How do you figure out which way to go?
The traditional answer is to ask one of them which direction the other would say, and then pick the opposite.
However, in _my_ puzzle, both of the people tell the truth, and the _sign_ is lying about that fact. (It might even by lying about only one question, who knows?) So everyone who tries to logic it ends up going the wrong way.
Also, there’s something else wrong with the puzzle as I stated it.Report
Yes, you have to include the information that Monty knows which door has the prize and which doors have the goat.
(Sorry, that’s a different puzzle that’s often mis-stated.)Report
Relevant
On topic bit starts at 5:20Report
Great puzzle!
Gur fbyhgvba vf cerggl fvzcyr. V tbg gur svefg dhrfgvba vafgnagyl. Gur frpbaq dhrfgvba jnf uneqre, fvapr lbh arrq n dhrfgvba “begubtbany” gb gur svefg. D1. Qb Rney naq Serq orybat gb gur fnzr gevor? Juvpu vf rdhvinyrag gb nfxvat jurgure gurer ner na bqq be rira ahzore bs gehgu gryyref. Lrf sbe bqq naq ab sbe rira. D2. Qb lbh orybat gb gur fnzr gevor nf rvgure Rney be Serq? Juvpu vf rdhvinyrag gb nfxvat vs gurer ner gjb be zber gehgu gryyref. Lrf sbe 2 be 3 gehgu gryyref, ab sbe 0 be 1.Report
Very nice, and a great explanation of why it works.
By the way, the custom here is to ROT13 answers, so people still working won’t see them by accident. I’ve taken the liberty of doing that to yours.Report
To wrap this up, there have been two correct sets of simple questions that meet the requirements. First was Alan Scott, with:
A1) Is exactly one of your friends a liar?
A2) Is either friend of the same type as you?
Next came BSEconomist with:
B1) Are your friends of the same type?
A2) Is either friend of the same type as you?
To see that these work, let’s consider all the possibilities:
All three are truth-tellers: A1 no, A2 yes, B1 yes
Dick is a truth-teller, as is one of the others: A1 yes, A2 yes, B1 no
Dick is a liar, and the others truth-tellers: A1 yes, A2 yes, B1 no
Dick is a truth-teller, the other two are liars: A1 no, A2 no, B1 yes
Dick is a liar, as is one of the others: A1 no, A2 no, B1 yes
All three are liars: A1 yes, A2 no, B1 no
Brandon had two questions that are correct, but more complicated:
1. Are you the sort who would say that there are an odd number of truth tellers?
2. Are you the sort who would say that the number of truth-tellers is fewer than two?
Asking “Are you the sort who would say X” results in the correct answer to X, so these questions lead directly to the number of truth-tellers.Report
Mike,
This reminds me of the stuff the philosopher/logician Raymond Smullyan wrote. “The Tao is Silent” was a favorite of my youth.Report
His “The Lady or the Tiger?” is one of my favorites. It has a lot of similar puzzles, but not this kind specifically. For instance, it has a place with four kinds of inhabitants:
* Sane humans, who have correct beliefs and tell the truth about them
* Insane humans, who have incorrect beliefs and tell the truth about them
* Sane vampires, who have correct beliefs and lie about them
* Insane vampires, who have incorrect beliefs and lie about them
So, if you ask someone “Are you a vampire?”, both kinds of insane ones say yes.Report
My favorite was this one on morality….
http://www.mit.edu/people/dpolicar/writing/prose/text/godTaoist.htmlReport