Knight, knave, commoner

868.4K Views

A king has a daughter and wants to choose the man she will marry.  There are three suitors from whom to choose, a Knight, a Knave, and a Commoner.  The king wants to avoid choosing the Commoner as the bridegroom, but he does not know which man is which.  All the king knows is that the Knight always speaks the truth, the Knave always lies, and the Commoner can do either.  The king will ask each man one yes/no question, and will then choose who gets to marry the princess.  What question should the king ask and how should he choose the bridegroom?

A followup question:

Suppose the three suitors know each other (an assumption that’s not needed in the original problem).  Then find a new strategy for the king where the king only needs to ask a question of any two of the three suitors in order to pick the bridegroom.

Share
ronret45 Expert Asked on 1st August 2015 in Microsoft Interview Puzzles.
Add Comment

  • 1 Answer(s)

    This can be the simplest answer for this question:

    If the King asks all three men the same question, “Are you the Commoner?”, he will receive one of two possibilities of answers. Either {Yes, No, No} or {Yes, Yes, No} or any permutation of the two. This is because the Knight will always answer “No”, the Knave will always answer “Yes”, and the Commoner will answer either “Yes” or “No”.

    At this point, the king only has the choose the unique answer in the set of answers he receives. If the answer was {Yes, Yes, No}, he will choose the man who answered “No” and his daughter will marry the Knight, if it was {Yes, No, No}, he would choose the man who answered “Yes” and his daughter would marry the Knave. Regardless, with this strategy, his daughter would never have to marry a commoner and the kingdom would be safe once again.

    Answer To The follow-up Question

    Think of each of the the three as A, B, and C.

    If we ask A and C, “Does B ever lie?”. We will receive 3 possibilities of answers { Yes, Yes}, {Yes, No}, or {No, Yes}. Notice we will never get {No, No}. This is because A and C could be:

    • Commoner and the Knight, meaning the Knight will Answer “Yes”
    • Commoner and the Knave, meaning the Knave will Answer “Yes”
    • Knight and the Knave, meaning they will never agree.

    If the King receives {Yes,Yes} from A and C, he should choose B.

    If the King receives {Yes, No} or {No, Yes}, he should choose the man who answered “Yes”.

    ronit Guru Answered on 5th August 2015.
    Add Comment
  • Your Answer

    By posting your answer, you agree to the privacy policy and terms of service.
  • More puzzles to try-