Knights and Knaves Puzzles

Knights and knaves puzzles were first formally introduced in Raymond Smullyan’s book What is the Name of This Book?: The Riddle of Dracula & Other Logical Puzzles. I won’t go too deep into their history as you will easily find that in many other sources.

The setting for these puzzles is an island, all of whose inhabitants are either knights or knaves. Knights always tell the truth (they never lie), while knaves always lie (they never tell the truth). A knights and knaves puzzle typically consists of a challenge to make a logical deduction based on the simplicity of the setting. I’ll explain myself better through some examples:

The following are the two basic examples found on Wikipedia and other web sources. John and Bill are residents of the island:

First example: John says “We are both knaves.” What are John and Bill?

Second example: John says “We are of the same kind,” after which Bill says “We are of different kinds.” What are John and Bill?

Testing all the four possible cases provides us with the answers to each of the two puzzles above. In the first one for example, the only possibility is that John is a knave and Bill is a knight. The second one also has only one possible solution which I will leave for my readers to figure out.

The most famous of all knights and knaves puzzles is much more difficult than the two examples above: At some point in your trip through the island, you are forced to choose between two doors, one of which is guarded by a knight while the other one is guarded by a knave. One of the doors leads to instant death while the other one allows you to continue with your tour. You don’t know which door is which, or which guard is which. You must make one (and only one) yes-no question to one (and only one) of the guards. After receiving the answer to your question, you must choose a door based on that answer. Which question would you ask and which door would you choose?

An even more difficult puzzle has been called The Hardest Logic Puzzle in the World, but for now I will just share with you some knights and knaves puzzles I came up with tonight. They may or may not be originally mine, but I devised them independently for this post. Andy, Bob, Carl, Dave and Evan are all residents of the island.

  • Can you figure out Bob’s kind by asking one yes-no question to Andy?
  • Can you figure out the number of knights among Bob, Carl, Dave and Evan by asking two yes-no questions to Andy?
  • How many yes-no questions do you need to ask Andy to figure out the number of knights among the five of them?

Have fun solving them! Remember to post your comments, questions, solutions and related puzzles in the comment section below.

About these ads

3 Comments

Filed under External, Logic, Original

3 responses to “Knights and Knaves Puzzles

  1. Joshua Sklar

    1. If I was to ask you what Bob was, what would you say?

    I’m not sure about the second one. If there is at least one knight, I think you could do it this way:

    First you ask, “If I were to ask you if there were an even number of knights among Carl, Bab, Dave and Evans, what would you say?” If he says yes, you ask “If I were to ask you if two of the four were knights, what would you say?”
    If he says no to this, you know there are four knights. If he says yes, there are two knights.

    If, on the other hand, he answers “no” to your first question, you can ask “If I were to ask you if there were three knights among them, what would you say?” If he answers “yes” to this, there are three. If he answers “no,” there is one.

    I do know about the last question. It seems to me, at this stage, that it would depend on his answers to the questions. I guess you could ask “If I were to ask you if the number of knights was a factor of six?” as the first question it could work out pretty well. If he says no, you’re only left with four and five, and then you could just ask, “If I were to ask you if there were four knights among you, what would say?” If he says no, they are all knights. If he says yes, there are four knights.

    If, on the other hand, he says yes, you have to narrow it down between one, two, and three, and I don’t know if you can do that in less than two questions. So, I’m going to say you need three tops, two minimum. Like the last question, this solution only works if there are more than zero knights.

  2. Lisa French

    Can you figure out Bob’s kind by asking one yes-no question to Andy?
    Yes, by asking “If I were to ask you if Bob was I knight, would you respond ‘Yes’?” An answer of yes means Bob is a knight, while an answer of no means Bob is a knave.

    Can you figure out the number of knights among Bob, Carl, Dave and Evan by asking two yes-no questions to Andy?
    Yes, by first asking “If I were to ask you if there is an even number of knights among Bob, Carl, Dave, and Evan, would you respond ‘Yes’?” An answer of yes means there is an even number, and an answer of no means there is an odd number. You should then ask “If I were to ask you if there is/are exactly 1 (if the first answer was no/odd)/2 (if the first answer was yes/even) knights among Bob, Carl, Dave, and Evan, would you respond ‘Yes’?” If the first answer was no and the second answer was yes then there is 1 knight. If both answers were yes then there are 2 knights. If both answers were no there are 3 knights. If the first answer was yes and the second answer was no then there are 4 knights.

    How many yes-no questions do you need to ask Andy to figure out the number of knights among the five of them
    I believe at least three. It has already been established that one can determine the number of knights among Bob, Carl, Dave, and Evan by asking exactly two questions. After doing so, you could ask Andy “If I were to ask you if you are a knight, would you respond ‘Yes’?” An answer of yes means he is a knight and you can add one to the number of knights among the other four residents which you determined with your first two questions, while an answer of no means he is not a knight and the number determined by your first two question represents the total number of knights among the five residents.

  3. Lisa French

    Regarding my above answer, I came to the realization that I neglected to consider the possibility of zero knights for the second question, which consequently led to my second and third answers to be incorrect.

    Instead, for the question “Can you figure out the number of knights among Bob, Carl, Dave and Evan by asking two yes-no questions to Andy?”, the answer should be:
    Yes, by asking Andy “If I were to ask you if you are a knight, would you respond ‘Yes’?” If he answers “Yes” then he is a knight and you may simply ask him how many knights there are among the others and he will provide a truthful answer. If he answers “No” then he is a knave and you must ask him “What is a number that is not equal to the number of knights among Bob, Carl, Dave, and Evan?” He will tell you precisely the amount of knights among them.

    For the question “How many yes-no questions do you need to ask Andy to figure out the number of knights among the five of them?”, the answer should be:
    At least two. To figure out the amount of knights among the five of them, you would follow the same steps as you did for the second question, but instead for the number of knights among all of them instead of just the other four.
    In other words, you would ask Andy “If I were to ask you if you are a knight, would you respond ‘Yes’?” If he answers “Yes” then he is a knight and you may simply ask him how many knights there are among the five of you. If he answers “No” then he is a knave and you must ask him “What is a number that is not equal to the number of knights among the five of you?”

    My answer to the first question “Can you figure out Bob’s kind by asking one yes-no question to Andy?” is the same:
    Yes, by asking “If I were to ask you if Bob was I knight, would you respond ‘Yes’?” An answer of yes means Bob is a knight, while an answer of no means Bob is a knave.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s