4
$\begingroup$

Here is a puzzle I have not yet been able to solve:

There are three people A, B and C who know each others identity.

You may pick A, B or C show him a logic statement (truth functional compounds only such as AND, OR, IF THEN, IF and only if) about their identities. (example: [A is a Knight OR B is Not a Normal])

He will then state whether or not the statement is true.

They can consist of:

Knights, who always tell the truth;

Knaves, who always lie;

Normals, who can do either one.

There can be at MOST one Normal.

The goal is to ask the fewest questions (each one directed at either A, B or C) to definitively identify all three.

I suspect there are many ways to approach the puzzle.

I have tried listing all possible combinations (30) of Knights, Knaves and Normals (that can tell the truth/lie), and then showing each one a statement. If I know the statement is true (A1=Knave) and I show it to a Knave who never tells the truth, I will get back a FALSE.

For my first question, I have shown A:

"[A is a Night AND B is NOT a Normal] OR [A is NOT a Night AND B is a Normal]. I use this because if I get a TRUE I know that B can't be normal, and if I get false it ends up that C can't be normal. This gave me my first stepping stone into the puzzle but you may think there is better.

Can you do it in 7 questions? (I have heard 5 is possible)

Please ask if you are curious/have more questions. Happy Thanksgiving!

Improve this question
$\endgroup$
1
  • $\begingroup$ ###I must make it clear. It is the number of questions addressed to an individual that is counted. If you ask one question, the following question does not change depending on the results of the first. Both those who answered TRUE and FALSE to the first question are asked the exact same second question.### $\endgroup$
    – Red
    Nov 28, 2015 at 23:40

3 Answers 3

Reset to default
2
$\begingroup$

Here's a way with six questions:

  1. Show A: "A is a Knight if and only if B is a Normal."
  2. Show B: "B is a Knight if and only if C is a Normal."
  3. Show C: "C is a Knight if and only if A is a Normal."
  4. Show A: "A is a Knight or A is a Knave."
  5. Show B: "B is a Knight or B is a Knave."
  6. Show C: "C is a Knight or C is a Knave."

The first three questions identify whether there is a Normal, and who it is if there is one:

  • If there are no Normals, all three answer FALSE.
  • If A is a Normal, B answers FALSE and C answers TRUE.
  • If B is a Normal, C answers FALSE and A answers TRUE.
  • If C is a Normal, A answers FALSE and B answers TRUE.

The other three questions identify each person who isn't a normal. A Knight answers TRUE while a Knave answers FALSE.

With the restriction that questions can't be changed based on earlier answers, five questions is impossible.

If we were able to use five questions to identify all three, then each of the 32 sequences of TRUEs and FALSEs should correspond to at most one assignment of identities. Either we ask one person three or more questions, or we ask two people two questions each.

Suppose we ask one person three questions. If that person is a Normal, they can answer whatever they want for those three questions, so each case takes up eight sequences of answers. There are four cases in which that person is a Normal. These cases would have to take up a a total of 32 sequences, leaving none for the cases in which that person is not a Normal.

Otherwise, we ask two people two questions each. Similarly, each case in which one of them is a Normal must take up four sequences of answers. There are eight cases in which one of them is a Normal, again taking up all 32 sequences.

Either way, we cannot use five questions to identify all three people.

Improve this answer
$\endgroup$
5
  • $\begingroup$ "Suppose you know that B is not a normal. Then you can show B a statement that must be true, like "B is a knight if and only if B is a knight", where the response identifies whether B is a knight or a knave." The problem is we propose one question to the full list of possibilities. That first question provides two paths, one where your statement proposed will work and the other where it has a different variable effect because it is Also, there is only 1 normal at MOST in this problem. You can have Knight Knight Knight or Knight Normal Knight, or Normal Knight Knight, etc. $\endgroup$
    – Red
    Nov 28, 2015 at 7:08
  • $\begingroup$ @Evan If your first question shows you that B is not a normal, then you proceed that way. Otherwise, your first question shows you that C is not a normal, and you ask similar questions to C instead. $\endgroup$
    – f''
    Nov 28, 2015 at 7:19
  • $\begingroup$ Yes I see. The difficulty then lies in using statements that work for each way no matter what happens~ As the puzzle is that your questions must lead you to the results no matter what the normals decide to say. Wiith enough statements you can sort out anything but the difficulty really lies in doing it in 7 or less. $\endgroup$
    – Red
    Nov 28, 2015 at 8:35
  • $\begingroup$ @Red Modified with a solution in 6 and a proof that 5 is impossible. $\endgroup$
    – f''
    Nov 29, 2015 at 4:45
  • $\begingroup$ I also came to a nearly identical proof, bravo! $\endgroup$
    – Red
    Nov 29, 2015 at 5:28
1
$\begingroup$

You need five questions. This works as follows:

Q1:
To A: You are a knight if and only if B is normal.

If A is a knight, then he answers yes if B is normal and no if he is not
If A is a knave, then he also answers yes if B is normal and no if he is not
If A is normal, then both B and C are not normal, so his answer does not matter then.
So this question gives you someone who is not normal (C if A answered yes, B if A answered no, regardless of what A is). All following questions are directed to this person.

Assuming B is not normal without loss of generality:
Q2:
To B: You are normal
A knight will answer no and a knave will answer yes. And since B is not normal, we now know what B is, and how to interpret his responses.

Q3:
To B: Either A or C is normal.
This tells you whether there is a normal

If there is not a normal:
Q4:
To B: A is a knight
Q5:
To B: C is a knight

which will tell you the other two.

If there is a normal:
Q4:
To B: A is normal
which tells you whether A or C is normal

Assuming A is normal, without loss of generality:

To Q5:
B: C is a knight
And this tells you the identity of C

Addendum: The question stated that there is at most one normal. If there is exactly one normal, it can be done in four questions. The protocol is the same, only you don't need Q3, since you already know the answer.

Improve this answer
$\endgroup$
0
$\begingroup$

This can be done in exactly five questions every time, provided your first question can find you at least one non-normal. Thanks to @Evan for already providing such a question.

Why is this helpful? Because now we could show our non-normal (let's assume it's B) any statement, XOR it with "B is a Knave", and be certain that our answer was the truth. As you can see, if B has to be a Knight or a Knave:

B Knight, XYZ True: [XYZ] XOR [B Knave] is True, so B says "True"
B Knight, XYZ False: [XYZ] XOR [B Knave] is False, so B says "False"
B Knave, XYZ True: [XYZ] XOR [B Knave] is False, so B says "True"
B Knave, XYZ False: [XYZ] XOR [B Knave] is True, so B says "False"

As a result, every statement can split the set of cases exactly in half by making a statement that is true for exactly half of them. And, conveniently, there are exactly 16 cases once we know somebody is not normal - again assuming B is not normal:

(A has 3 choices) x (B has 2 choices) x (C has 3 choices) = 18 possible cases, but Normal Knave Normal and Normal Knight Normal break the rules, so only 16 of those cases are valid.

Thus, our initial question statement leaves us with 16 cases, a second statement (if well chosen) can leave us with 8 cases for each answer, the third leaves us with 4 per set of answers, the fourth leaves us with 2, and the fifth uniquely identifies our situation. Now that we know it's possible, we simply need to find a set of statements that encompasses all possible strings of true/false answers - which, for five consecutive statements is 2^5 = 32 possibilities. I'll be going for simplicity over clarity, so my statements will not all follow the form "XYZ" XOR "Letter is a Knave", though they could be formatted as such if one wished.

I'll create some notation here for efficiency:

[Number][Truth Values][Person]:[Statement]

This is the [Number]'th statement shown, in the event that the previous sequential answers were the [Truth Values] indicated, it is being shown to [Person], and the statement is [Statement]. If one can determine all of the roles given a resulting truth value for a statement, I will denote it as:

[Number][Truth Values][Person][Single Truth Value] - [A Role], [B Role], [C Role]

Where [Single Truth Value] was [Person]'s response to statement [Number] with previous answers of [Truth Values]. Note that a conclusion may show up multiple times by way of different paths.

[Letter] [Role] is an assertion that [Letter] is [Role]

Example:

A is a Normal

I ask A if A is a Knight, and A says Yes. I ask A if A is a Knight a second time, and A says No. This is recorded as:

1A: [A Knight]
2TA: [A Knight]
2TAF - Normal

Now, the statements:

1A: [A Knight AND B NotNormal] OR [A NotKnight AND B Normal]
2TB: [A Knave OR C Normal] XOR [B Knave]
3TTA: [B Knight] XOR [A Knave]
4TTTB: [C Normal]
5TTTTB: [A Knight]
5TTTTBT - Knight, Knight, Normal
5TTTTBF - Knave, Knight, Normal
5TTTFB: [C Knight]
5TTTFBT - Knave, Knight, Knight
5TTTFBF - Knave, Knight, Knave
4TTFB: [C Normal]
5TTFTB: [C Knight]
5TTFTBT - Knave, Knave, Knave
5TTFTBF - Knave, Knave, Knight
5TTFFB: [A Knight]
5TTFFBT - Knave, Knave, Normal
5TTFFBF - Knight, Knave, Normal
3TFB: [C Knight] XOR [B Knave]
4TFTC: [A Knight]
5TFTTC: [B Knight]
5TFTTCT - Knight, Knight, Knight
5TFTTCF - Knight, Knave, Knight
5TFTFC: [B Knight]
5TFTFCT - Normal, Knight, Knight
5TFTFCF - Normal, Knave, Knight
4TFFC: [A Knight]
5TFFTC: [B Knight]
5TFFTCT - Normal, Knave, Knave
5TFFTCF - Normal, Knight, Knave
5TFFFC: [B Knight]
5TFFFCT - Knight, Knave, Knave
5TFFFCF - Knight, Knight, Knave
2FC: [A Knave OR B Normal] XOR [C Knave]
3FTA: [C Knight] XOR [A Knave]
4FTTC: [B Normal]
5FTTTC: [A Knight]
5FTTTCT - Knight, Normal, Knight
5FTTTCF - Knave, Normal, Knight
5FTTFC: [B Knight]
5FTTFCT - Knave, Knight, Knight
5FTTFCF - Knave, Knave, Knight
4FTFC: [B Normal]
5FTFTC: [B Knight]
5FTFTCT - Knave, Knave, Knave
5FTFTCF - Knave, Knight, Knave
5FTFFC: [A Knight]
5FTFFCT - Knave, Normal, Knave
5FTFFCF - Knight, Normal, Knave
3FFC: [B Knight] XOR [C Knave]
4FFTB: [A Knight]
5FFTTB: [C Knight]
5FFTTBT - Knight, Knight, Knight
5FFTTBF - Knight, Knight, Knave
5FFTFB: [C Knight]
5FFTFBT - Normal, Knight, Knight
5FFTFBF - Normal, Knight, Knave
4FFFB: [A Knight]
5FFFTB: [C Knight]
5FFFTBT - Normal, Knave, Knave
5FFFTBF - Normal, Knave, Knight
5FFFFB: [C Knight]
5FFFFBT - Knight, Knave, Knave
5FFFFBF - Knight, Knave, Knight

To use this list, just show the first statement to the indicated person (in this case, A) - if you get a T, jump to 2T and show that statement to the indicated person, if you get a false, jump to 2F and show that statement to that indicated person instead. Continue on until you get an answer for your fifth statement, all possibilities of which lead to conclusions. You can test the veracity of these conclusions by picking any case (A = ?, B = ?, C = ?) and running through the questions to confirm that you end up at the correct conclusion.

Improve this answer
$\endgroup$
13
  • $\begingroup$ This is very comprehensive thank you for your thoughts. Can you come up with a logic statement of identity that equates to "this statement will be a lie?" The way it the puzzle is put forth, we can only show statements of identity. I was thinking something along the lines of A is not a Knave OR a Normal ? $\endgroup$
    – Red
    Nov 28, 2015 at 7:02
  • $\begingroup$ Hmm... well, it has to be self-referential in order to work, because we need to cancel out their internal truth/lie to just get the truth value of the question. That's trick to do in a single statement as soon as normals become a possibility, since you can't just XOR with "you are a knave". I suspect that if you only allow direct references to Knave/Knight/Normal, you'll need every question to reference two people, and sort out the mess at the end... I'll see if I can get that to work. $\endgroup$
    – Zerris
    Nov 28, 2015 at 7:18
  • $\begingroup$ Yes, as I attempted it using an excel document, I noticed whenever a statement I proposed could be interpreted or TRUE or FALSE by the normal, I carried that normal across and then had to take into account again the ability to say true or false again, even though I only carried across the case where it said either TRUE or FALSE. Eh it's really hard to explain, but I'm eager to see what you come to. $\endgroup$
    – Red
    Nov 28, 2015 at 8:41
  • $\begingroup$ Looks like you can make it a maximum of six questions, but can't limit it down to five in all cases. I finished up a quarter of the lines, but it's pretty time consuming. I can do the rest if you like, but it's just brute force; there's little elegance to it. $\endgroup$
    – Zerris
    Nov 28, 2015 at 8:57
  • $\begingroup$ Correction half the lines. Also, I do notice I have exactly one case that resolves at question 4, and one case that needs a 6th question, so maaaaybe you can change your specifically excluded case in 2TB to something that balances those out into both being 5-question problems... but I strongly doubt it; in my experience, one of your chains will just get too many normals in it and go to six. $\endgroup$
    – Zerris
    Nov 28, 2015 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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