I would like to try more strict conditions for puzzle, which frodoskywalker solved so simply. Basically all the same, but only one type of questions is allowed.
- We have T Knights (truth-tellers), L Knaves (liars) and R Jokers (random-tellers). $T > 0$. We know all 3 numbers, but we do not know who is who.
- We can chose any two of them and ask the first about the second one "Is he a Knight?". We can repeat this questioning procedure any number of times.
- We need to find one Knight.
How must T, L and R be related to make the task possible to complete?
My analysis:
1. If $T+L \le R$ it is impossible. $T$ jokers can simulate Knights, $L$ Knaves and we would never be able to distinguish between them and find a real Knight.
2. If $T>R+L$ the task is possible. It is possible with $L = 0, T > R$ and we can treat Knaves as Jokers.
3. If $R=0, L = T$ then this is impossible.
Indeed, if you get an answer "Yes", then there is two possibilities: "Kni Kni" or "Kna Kna" (both Knights or both Knaves). If we get "No", then it is either "Kni Kna" or "Kna Kni". From this we can see that if we replace all Knights by Knaves and vice versa we will get exactly the same answers. So even if we are able to divide them all into two groups according to their type we will never know who is who.
4. If $R=0, L > T$ then it can be solved in exactly the same way as for $L=0, T > R$ case:
We need to exclude all pairs who answer "No" and create a chain of "Yes" longer then half of the not excluded people. Then the last in the chain will be a Knave. Just ask him about all the rest until you hear "No".
So the question is what happens when $R \neq 0$, $L>R-T$ and $L \ge T - R$. For example, when $L = 1, T = R = 10$.
Answer
We must have $L + T > R$ and $T \neq L + R$.
The distinguishing feature of knights is that they form a group of $T$ people who identify one another as knights and everyone else as not knights. We only have trouble if we have two groups of people who do that.
If $T = L + R$, and the jokers always lie, then the set of non-knights will be indistinguishable from the set of knights.
From here down, consider only cases where $T \neq L + R$. In this case, the group of knights identify $T$ people as knights and the knaves identify $L+R \neq T $ people as knights, so we can separate those groups.
The only way to have confusion is if we have a group of $T$ jokers who identify one another as knights and everyone else as not knights. This can only happen if $T \leq R$.
In this case, we have two groups of potential knights and everyone else, who is potentially a knave. The potential knaves have $L$ knaves and $R-T$ jokers. If $L > R-T$, then we know most of the potential knaves will reliably lie about the groups of potential knights, so we can identify which group are the actual knights.
If $L \leq R-T$, then we can have a set of $L$ jokers who tell the truth about the people in the two sets of potential knights, which is the opposite of what the $L$ knaves say. Thus, we cannot identify which group of potential knights are the actual knights.
Reiterate: We have ambiguity if:
A. We have $T = L+R$ and all the jokers lie.
B. We have one group of $T$ jokers who all claim everyone in that group is a knight and everyone else is not and we also have another group of $L$ jokers who tell the truth about the knights and the first set of jokers, but lie about everyone else.
In any other case, we can distinguish which group are the real knights. Thus, the problem is solvable if $L + T > R$ and $T \neq L + R$.
No comments:
Post a Comment