You are on a fictional island with two types of people: knights who always tell the truth, and knaves, who always lie. Three of the inhabitants - A, B, and C are standing in the garden. A says, "B and C are of the same type" (B and C are both knaves or are both knights.) Someone then asks C, "Are A and B of the same type?" What does C answer?
$\begingroup$
$\endgroup$
4
-
5$\begingroup$ Obligatory XKCD reference... $\endgroup$– Mr ListerCommented Sep 25, 2019 at 12:23
-
$\begingroup$ Obligatory secondary XKCD reference... $\endgroup$– ojdoCommented Sep 25, 2019 at 14:09
-
$\begingroup$ another xkcd reference(though this one only matches by having an island...) $\endgroup$– BaldrickkCommented Sep 25, 2019 at 16:40
-
$\begingroup$ Does this answer your question? Solve the following knights and knaves problem $\endgroup$– Jeff ZeitlinCommented May 20, 2022 at 18:57
Add a comment
|
10 Answers
$\begingroup$
$\endgroup$
3
C will answer "Yes".
Assume A is a knight. Then B and C are either both knaves or both knights.
* If they are both knights, then all three are knights, and A and B are both therefore knights, and C will truthfully say that they are the same.
* If B and C are both knaves, then A and B are different, and C will lie and say they are the same.
Assume A is a knave. Then B and C are knight/knave or knave/knight.
* If C is a knave, then A and B are different, and C will lie and say they are the same.
* If C is a knight, then A and B are the same, and C will truthfully say they are.
Thus, regardless of what the status of A and B are, C will answer that they are the same.
answered Sep 23, 2019 at 15:23
-
2$\begingroup$ This is where this intuitively felt like it was going. But I didn't finish the full logical exhaustion of possibilities. $\endgroup$– CruncherCommented Sep 23, 2019 at 18:14
-
1$\begingroup$ @Cruncher but there are only 4 possibilities... $\endgroup$– KrupipCommented Sep 25, 2019 at 15:31
-
2$\begingroup$ @opa Which is a lot to keep straight in your head. $\endgroup$– CruncherCommented Sep 25, 2019 at 16:14
$\begingroup$
$\endgroup$
3
A shortcut to get the correct answer, assuming that one exists, is to simply assume that A, B and C are all knights, and thus speak the truth. In this case, C will obviously answer "Yes." And since the question implicitly assumes that C's answer is the same for any possible scenario, C must always answer "Yes."
This, by the way, is a very handy exam-taking trick. Quite often, especially with questions like this that seem to provide too little information but still expect a definite answer, just knowing that an answer exists can make the problem much easier to solve. In particular, it means that you can freely assume any self-consistent set of values for any unspecified parameters (such as, in this case, the types of the people involved), since any choice of those unspecified parameters must necessarily yield the same answer.
Of course, with real-world problems, one cannot generally assume that answer necessarily exists. (See e.g. this Q&A on Mathematics Educators Stack Exchange for some nice counterexamples.) Even so, sometimes it can be easier to first start with that assumption, figure out what the answer has to be if there is one, and only then try to check that the candidate answer really works in all cases. For example, in the context of this puzzle, knowing that C says "yes" in one possible scenario means that, to verify that the puzzle really has a solution, we just need to check that any scenarios where C would say "no" are not possible.
answered Sep 24, 2019 at 20:26
-
6$\begingroup$ Great answer. To aboid that the opener could have asked: will he always give the same answer? And if yes: what will it be? $\endgroup$– TodeCommented Sep 24, 2019 at 22:01
-
3$\begingroup$ Excellent lateral thinking. $\endgroup$ Commented Sep 25, 2019 at 14:41
-
4$\begingroup$ It is absolutely possible that the right exam answer is "we don't know how C will answer, based on the information we were given". $\endgroup$ Commented Sep 25, 2019 at 21:27
$\begingroup$
$\endgroup$
1
The easiest way to find the solution is to write the Truth Table listing all the possibilities whether a person tells lies or tells the truth:
A B C
1 lie lie lie
2 lie lie truth
3 lie truth lie
4 lie truth truth
5 truth lie lie
6 truth lie truth
7 truth truth lie
8 truth truth truth
A says "B and C are of the same type", and by this statement we can remove impossible combinations i.e. #1 and #4 (B and C being of the same type with A lying) and #6 and #7 (B and C being of a different type with A telling the truth). We are left with:
A B C
2 lie lie truth
3 lie truth lie
5 truth lie lie
8 truth truth truth
Now, if we ask C "Are A and B of the same type?", we can easily see he always replies yes.
-
1$\begingroup$ Thanks to @Rand al'Thor and all the others for the edits! $\endgroup$– dr_Commented Sep 25, 2019 at 5:48
$\begingroup$
$\endgroup$
3
Suppose we refer to knights and true statements as "even" and knaves and false statements as "odd". Then the statement "Knights always tell the truth" and "Knaves always tell lies" can be recast as "A person and their statement always add up to even" (even + even is even, odd + odd is also even). Two people have the same type iff they add up to even. So A will say "B and C are the same type" only if the sum of "B and C are the same type" and A is even, i.e. A+(B+C) = even. This is completely symmetrical with respect to A, B, and C, so if A says "B and C are the same type", then C will say "A and B are the same type."
-
1$\begingroup$ This was my reasoning as well. It's awful hard to explain, though - I suspect it needs to be explained more clearly, though I'm not sure how. $\endgroup$ Commented Sep 24, 2019 at 13:20
-
1$\begingroup$ This can be generalised to any number of people if the question is instead "Excluding yourself, are there an even number of knights here?", which is logically equivalent to the original for three people. $\endgroup$– ZandarCommented Sep 25, 2019 at 7:11
-
1$\begingroup$ @Zandar That comment also gives a neat simplification of the thought process in this answer: A knight's and a knave's answer to "Excluding yourself, are there an even number of knights here?" is actually an honest answer to "Are there an odd number of knights here in total?" So we immediately see that everyone answers that question the same way. $\endgroup$– JiKCommented Sep 25, 2019 at 21:21
$\begingroup$
$\endgroup$
I would use simple propositional logic for problems of this type. Let $a,b,c$ represent 'A is a knight', etc, and let $x$ stand for an arbitrary person so that $$ x\text{ says }\unicode{x201c} P \unicode{x201d} \implies (x \equiv P) $$ Then...
...the first statement implies $a \equiv (b \equiv c)$, and the second implies $c \equiv ((a \equiv b) \equiv r)$, where $r$ is C's response.
Now since $\equiv$ is associative and symmetric, substituting the first in the second simplifies to $r \equiv \text{true}$, i.e., C's response is "Yes."
answered Sep 26, 2019 at 10:01
$\begingroup$
$\endgroup$
Suppose A is a knight.
Then either B and C are both knights, or B and C are both knaves.
If B and C are both knights, then C would truthfully reply that A and B are of the same type. So C would say "yes".
If B and C are knaves, then C would lie that A and B are of the same type. So C would say "yes".
Suppose A is a knave.
Then A lies when he says that B and C are of the same type. Thus B and C are of different types.
Suppose B is a knave and C a knight. Then C truthfully replies that A and B are of the same type. So C says "yes".
Suppose B is a knight and C a knave. Then C lies when he says A and B are of the same type. So C says "yes".
This covers all scenarios, so we can say that C will always say "Yes, A and B are of the same type".
$\begingroup$
$\endgroup$
If A is a Knight, then he is telling the truth, and both B and C are of the same type. This gives us two possibilities: that B and C are both Knights, or that B and C are both Knaves.
If B and C are both Knights, then that means C is a Knight, and C must tell the truth. Since B is a Knight and A is a Knight, C will truthfully tell us that yes, they are the same type.
If B and C are both Knaves, then that means that C is a Knave, and C must tell a lie. Since B is a Knave and A is a Knight, C will falsely tell us that yes, they are the same type.
Now consider the possibility that A is a Knave. In this case, A is telling a lie, and B and C are not the same type, and must in face be two different types. This gives us two possibilities: that B is a Knight and C is a Knave, or that B is a Knave and C is a Knight.
If B is a Knight and C is a Knave, then C must tell a lie. Since A is a Knave and B is a Knight, C will tell us that yes, they are the same type, even though they are not.
If B is a Knave and C is a Knight, then C must tell the truth. Since A is a Knave and B is also a Knave, C will tell us that yes, they are the same type.
As you can see, every possible combination results in C telling us yes, A and B are the same type. Now, whether he's lying or not is another story entirely.
$\begingroup$
$\endgroup$
1
If a knight is 0, and a knave is 1, then A's statement tells us that A + B + C is even. And C answering "Yes" means the same thing, by symmetry. (And "No" would mean A+B+C is odd.) So C must answer "Yes".
(Logically, this is similar to the answers of Accumulation, Neil, and Marnix Klooster.)
-
$\begingroup$ And to mine, if you write A+B+C as $A \not\equiv B \not\equiv C$ which is equivalent to $A \equiv B \equiv C$. $\endgroup$ Commented Sep 28, 2019 at 19:05
$\begingroup$
$\endgroup$
2
Let A, B and C be represented by "true" and "false" instead of "knight" and "knave". Then the act of A answering a proposition P is the result of the exclusive nor (xnor) of A with P. Conveniently, the proposition "are B and C of the same type" is also an xnor operation, so A's final answer is given by (A xnor (B xnor C)). However, the xnor operation is associative and commutative, so this can be written ((A xnor B) xnor C), which is the result of C answering the proposition "are A and B of the same type". This means that C's answer is always the same as the answer A gave.
-
1$\begingroup$ Note that 'exclusive nor' is just a convoluted way to say 'equals'. :-) $\endgroup$ Commented Sep 26, 2019 at 10:00
-
$\begingroup$ See also page 59 of Dijkstra&Scholten, "Predicate Calculus and Program Semantics" (Google Books link). $\endgroup$ Commented Sep 26, 2019 at 10:44
$\begingroup$
$\endgroup$
The puzzle doesn't actually state that each of A, B or C know what type the others are.
But in this case we do know that A knows what type B or C are (because neither knight nor knave would make a statement that they don't know to be true or false. )
So either A is a knight and B, C are of the same type, or A is a knave and B, C are of different type. We know that, C knows that, and C knows his own type, so according to the previous analysis, C would say they are both of the same type.
It would have been different if A had said "I know that B and C are of the same type". A could be a knight, but A might also be a knave who doesn't know either B's or C's type. Even if C knows his own type, if he doesn't know B's type then A's statement doesn't give him that information.
So C wouldn't know B's type. If C is a knight he would say "I don't know if A and B are of the same type". If C is a knave he can't say "A and B are of the same / of different type", because he doesn't know if that statement would be true or false. He can say either "I know that A and B are of the same type", or he can say "I know that A and B are of different type".
