1
$\begingroup$

Following these questions: Faulty computers, Knights and jokers I wonder, what if the conditions are the following:

  1. 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.
  2. 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.
  3. 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$.

$\endgroup$
  • $\begingroup$ related paper: ma.rhul.ac.uk/~uvah099/Maths/ksDRev2.pdf $\endgroup$ – d'alar'cop Oct 21 '14 at 10:12
  • $\begingroup$ @d'alar'cop, there liars wasn't mentioned, right? $\endgroup$ – klm123 Oct 21 '14 at 10:17
  • $\begingroup$ correct, but it may help people get going $\endgroup$ – d'alar'cop Oct 21 '14 at 10:25
  • $\begingroup$ Do we have as many questions as we wish? $\endgroup$ – frodoskywalker Oct 21 '14 at 11:07
  • $\begingroup$ @frodoskywalker, yes. $\endgroup$ – klm123 Oct 21 '14 at 11:39
3
$\begingroup$

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<T+L$, so long as T>0 (because there must be a knight to identify).

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<T+L$. As before, identify the (apparent) knaves. They will form groups - identifying every 'knave' within their group as a knave and every 'knave' outside their group as a joker. The groups may be as small as 1 person.

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<T+L$.

$\endgroup$
  • $\begingroup$ Note that as long as $T+L>R$, we only need 1 knight, and that is only because of condition 3. $\endgroup$ – frodoskywalker Oct 21 '14 at 13:16
  • $\begingroup$ Could you explain this sentence? : "... you exclude them and take the majority claim of the remainder about the alleged knaves." I am foreign and it is too hard to understand for me. $\endgroup$ – klm123 Oct 21 '14 at 14:04
  • $\begingroup$ I mean that you ignore the group known not to be knights (the knaves and jokers pretending to be knaves) and confined your further questions to the other people, who are now guaranteed to have a majority of knights. $\endgroup$ – frodoskywalker Oct 21 '14 at 14:28
  • $\begingroup$ This will work only if T > R. For that case we already have solution. $\endgroup$ – klm123 Oct 21 '14 at 14:56
  • 1
    $\begingroup$ I see. You simply divide the group on two parts and at least one part will have less than 50% jokers. $\endgroup$ – klm123 Oct 21 '14 at 16:12
0
$\begingroup$

Speedup on above: (Provided T+L > R, but you don't need to know those numbers.)

  • First, find a consistent person (knight / knave):
    • Start with a solution to the "Find a knight among a mixture of knight / jokers." ( Knights and jokers )
      • Where the above would have you ask A "Is B a knight?", instead ask A "Is B a knight?" then "Is B a knave?".
        • If you get opposite answers, treat it as though A said B is a knight.
        • If you get the same answer to both questions, treat it as though A said B is not a knight. (This takes less than 2(T+L+R) questions.)
    • Call this person C.
      • If any person J has claimed C is inconsistent, that person must be a joker. Ask C whether J is a knight to determine whether C is a knight or knave.
      • If not, pick a person P and ask C "Is P a knight? Is P a knave? Is P a joker?". This enable you to deduce the types of P and C.
    • If C is a knight, you can stop. Otherwise, just ask C whether each person is a knight until you get a "no" answer.
  • Total questions: About 3(T+L+R).

(If you don't want to use any "Is __ a joker?" questions, then ask C "Is __ a knight? Is __ a knave?" until you get two same responses. This will reveal whether C is a knight or knave. As long as there is at least one joker, this will eventually work, with about 4(T+L+R) questions.)

If you don't care about minimizing number of questions, ask each person whether each other person is a knight, then whether each other person is a knave. Take the largest subset such that each member gives opposite answers to every pair of questions about every other member.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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