Following these questions: Faulty computers, Knights and jokers I wonder, what if the conditions are the following:
- 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 of the 3 possible questions "Is he a Knight/Knave/Joker?". We can repeat this questioning procedure any number of times.
- We need to find one Knight.
How N, M and K must be related to make the task possible to complete?
It is clear for me, that $T+L>R$. Otherwise $T$ jokers can simulate Knights, $L$ Knaves and we would never be able to distinguish between them and find a real Knight.
Also we know already that if $L = 0, T > R$ the task is possible. Also it is obviously possible if $T>R+L$, because we can treat Knaves as Jokers.
So the question is what happens when $L>R-T$ and $L \ge T - R$. For example, when $L = 1, T = R = 10$.
Answer
Let's assume the jokers are intelligent, coordinated and aware of our strategy. If they fail to meet these conditions they only make it easy for us.
Edited for clarity This works for any $R
Step one is to identify the knave(s) by the fact that they will say 'yes' to 2 of the three questions for any given person ("Is bob a knave?", "Is bob a knight?", "Is bob a joker?"). If you conclusively identify a knave you have won - you just take the reverse of their statements to be true.
Ask each person if their neighbour is a knight, a knave, a joker. Knights will say 'yes' once. Knaves will say yes twice. An identified knave is effectively a truth teller - you can use them to identify everyone else.
This means that the jokers must use L jokers to impersonate the knaves. You now have a set of at least 2L alleged knaves who you know are not knights. This means the rest of the people - everyone who has not acted as a knave - have a majority of knights. You then ask all of those people about someone outside this group. The majority will be telling the truth. Continue this until you identify a liar, who you can use to identify everyone else.
Edit again: The jokers must impersonate the entire group of knaves. If you know there are 2 knaves and you see three people acting as knaves, ask each one about the identity of the other 'knaves'. The two genuine knaves will identify the joker (one you account for their backwards answers) and by extension themselves.
Yet another edit If you don't know the values of T,L,R you can still do it so long as $R Next, have the apparent knights identify all other apparent knights. They will, again, form groups. Have the knight groups identify the knave groups. They will form what I'll call "coalitions" - groups of knights and knaves who mutually identify each other and identify anyone in another coalition as a joker. The largest coalition must be the one with knights and knaves, given $R
No comments:
Post a Comment