9
$\begingroup$

Premise

A Knight always tells the truth. A Knave always lies. A Normal may either lie or tell the truth. You are allowed to ask questions that can be answered with “yes” or “no”, such as “Is this person a Normal?”

Question

There are four people in front of you. One is a Knight, another one is a Knave, and the other two are Normals. They all know the identities of one another. Prove that the Normals may agree in advance to answer your questions in such a way that you will not be able to learn the identity of any of the four people.

My solution

Both normals will act as if the first is a knight, both the knight and the knave are normals and the other normal is a knave. This creates perfect symmetry between the two normals and the two normals and between the other pair so it is impossible to distinguish (I think a formal proof by contradiction could be constructed).

Given solution

The first Normal will act as though he is a Knight while the second Normal will act as though he is a Knave. Then we cannot tell the difference between the first Normal and the Knight, nor between the second Normal and the Knave.

I think I could break this solution by first asking a statement which is trivially true like "is 1+1=2?". This would allow me to narrow down to the two people who could possibly be knights. Then I could ask these two potential-knights whether each of the other two are knaves. They should both correctly tell me who the knave is and who the normal is because they both tell the truth. Then I could do the opposite to work out who the correct knight is.

  • Am I correct that this solution is flawed?
  • Is my solution correct?
$\endgroup$
7
  • $\begingroup$ One thing came to my mind as I was reading this: do normals always answer either truthfully or deceptively? What I mean is: if a normal answers the first question truthfully, does that mean they will always answer truthfully after that? $\endgroup$
    – Kman3
    Aug 25, 2020 at 3:09
  • $\begingroup$ @Kman3 I inferred that they can answer either way to satisfy whatever hidden agenda they may have. They are 'normal' like us. $\endgroup$ Aug 25, 2020 at 3:11
  • $\begingroup$ I see. I think that eliminates your objection to the given solution, though, because you couldn't have a justification for believing that both people who tell you 1+1=2 are (always) telling the truth. I have to say though, both your and the given solution are very difficult to follow because I don't see what logic is being used to make each determination. Someone may understand this better, though. $\endgroup$
    – Kman3
    Aug 25, 2020 at 3:15
  • $\begingroup$ I believe you are correct on both counts. Label each person $1$ through $4.$ We may narrow down whether each of $1, 2, 3,$ and $4$ is not a Knight or Knave by asking a question like "does $1 + 1 = 2$?" In either your solution or the sample solution, you will find that there are two people who can be Knights, and two who can be Knaves. Let's say that $1$ and $2$ are potential Knights, and $3$ and $4$ are potential Knaves. Then, ask each of $1$ and $2$ "is $3$ a Knave?" and "is $4$ a Knave?" $\endgroup$
    – Stahl
    Aug 25, 2020 at 4:49
  • $\begingroup$ [continued] Both will tell you "yes" to one of these questions and "no" to the other (say "yes" to $3$ and "no" to $4$). Since one of them was definitely a Knight, you know that at least one of them is telling the truth; therefore $3$ is a Knave and $4$ is a Normal. So, you've found the Knave, and this does not work. (As you say, you can indeed figure out all their identities by asking the Knave "is $1$ a Knight?" and "is $2$ a Knight?" knowing it will lie.) So, if the given solution means that one Normal will tell the truth about everything, even the other Normal, it won't work. $\endgroup$
    – Stahl
    Aug 25, 2020 at 4:50

1 Answer 1

2
$\begingroup$

Yes, your solution is correct (and the one you read is not); my guess is that the original puzzle was authored by someone who had your solution in mind, and the source you read it from lazily mistranscribed the original (correct) solution without thinking through whether their phrasing of it made sense.

As an extension of this problem, we might ask when you can determine the identities of a collection of $k$ knights, $v$ knaves, and $n$ normals.

By your argument, we will fail if $n\ge k+v$; $k+v$ of the normals can pretend like their roles are reversed with the knights and knaves, and the remaining normals (if any) can just answer "yes" to all questions asked of them.

But is it possible when $n < k + v$? I'll provide an answer below, but feel free to stop here if you want to ponder it yourself.


The answer is that it is indeed possible to root out the normals in this case. For each person $P$, we ask everyone present the following question:

"If I asked you if $P$ were normal, would you say yes?"

If $P$ is normal, knights will truthfully inform you that they would tell you so and say "yes", while knaves will lie about the fact that they would have said no, and so also say "yes". Conversely, knights and knaves will both say "no" to this question if $P$ is not normal. So every knight and knave's answer will line up with whether $P$ is normal or not. Then to figure out if $P$ is normal or not, just take the majority response - since the knights and knaves always concur and outnumber the normals, their answer will be the correct one, and there aren't enough normals to overthrow the vote no matter what they say.

By repeating this procedure for each person $P$, we obtain an answer for everyone present (and we can do it again with "knight" instead of "normal" if we want to specify things further). In fact this algorithm works so long as you know that $n<k+v$ - you don't have to know their exact values to correctly identify everyone present.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.