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!
Answer
Here's a way with six questions:
- Show A: "A is a Knight if and only if B is a Normal."
- Show B: "B is a Knight if and only if C is a Normal."
- Show C: "C is a Knight if and only if A is a Normal."
- Show A: "A is a Knight or A is a Knave."
- Show B: "B is a Knight or B is a Knave."
- 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.
No comments:
Post a Comment