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?
Best Answer
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 $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.