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?" (a) There are three people in front of you. One is a Knight, another one is a Knave, and the third one is a Normal. They all know the identities of one another. How can you too learn the identity of each? (1) (b) 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. (3)
Problem
Source:
Tags: combinatorics
Nguyenhuyhoang
26.08.2024 02:47
For part (a), we ask the question "Are you a Normal?" to all three people. A Knight will always answer No and A Knave will always answer Yes. So, regardless of how the Normal answers, we can always find 2 people answering Yes and 1 person answering No or 2 people answering No and 1 person answering Yes. Without the loss of generality, assume that there is 1 person answers No, we know that person has to be the Knight. Since the Knight is always truthful, we can ask the Knight the identity of the other people. Hence, we can always tell the identities of 3 people. For part (b), if the player can tell the identity of 1 person in the group then either the player can reduce to part (a) or the problem is done if the identity of the person is a Knight or a Knave, so the Normals have to try their best to prevent this. The Normals can use the following strategy: for a question Q, if the Knight and the Knave answer differently then the Normals will answer differently from each other and randomly match the answer of the Knight or the Knave, otherwise they will answer the same answer with the Knight and the Knave. With this strategy, the player cannot tell the Normals from the Knight and the Knave.