Results 1 to 10 of 10
Like Tree1Thanks
  • 1 Post By romsek

Thread: Knights - knaves puzzle

  1. #1
    Newbie
    Joined
    Jun 2016
    From
    USA
    Posts
    12

    Knights - knaves puzzle

    On a fictional island there are 10 inhabitants, who all know each other, of which 5 are knights, who always tell the truth and the rest of them are knaves, who always lie.
    A visitor to the island wants to determine the 5 knaves. What is the minimum number of yes-no questions he must ask the inhabitants in order to find the 5 knaves?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,693
    Thanks
    546

    Re: Knights - knaves puzzle

    You ask the clever question of the each person you meet, which allows you to determine what he is. Do this at most nine times and you have identified all five of one group. Once you have your clever question, you use the Pigeonhole Principle to prove that you need no more than nine questions.

    Edit: The clever question is not remotely clever.
    Last edited by Archie; Dec 7th 2016 at 08:07 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2016
    From
    USA
    Posts
    12

    Re: Knights - knaves puzzle

    and what is this "clever question"? What do you mean "is not remotely clever"?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,259
    Thanks
    2239

    Re: Knights - knaves puzzle

    Quote Originally Posted by Alderamin View Post
    and what is this "clever question"? What do you mean "is not remotely clever"?
    one would be

    If I was a knight would you call me a knight or a knave? Or some such.

    Get them to respond about a given fact.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,693
    Thanks
    546

    Re: Knights - knaves puzzle

    Quote Originally Posted by romsek View Post
    Get them to respond about a given fact.
    "Are you wearing a hat?" or "Can you fly?" would do.

    We might be able to do better by treating groups. I'm thinking of the sort of puzzle where you have a balance and number of balls and one (or in this case) half is either heavier or lighter than the rest.

    The question "does this group have more knights than that group" is putting the groups on the balance. The problem is that a balance answers in ternary, not binary.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,259
    Thanks
    2239

    Re: Knights - knaves puzzle

    Quote Originally Posted by Archie View Post
    "Can you fly?" would do.
    and wouldn't you be surprised when they answered yes and flew off!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Feb 2014
    From
    United States
    Posts
    1,654
    Thanks
    781

    Re: Knights - knaves puzzle

    Ask A "Would you say that you are a knight if you were asked whether you are a knight or a knave?"

    If A is a knave, he would falsely answer "knight" if asked about his status so he will falsely answer "no" to the hypothetical question. If A is a knight, he will truthfully answer "knight" if asked about his status so he will truthfully answer "yes" to the hypothetical question.

    If A answers "no," you have identified one knave. So you could round up B, C, D, and E and ask A whether they are all knaves. If the answer is "no," then A, B, C, D, and E are the knaves. If A answers "yes," you have identified one knight. So you could round up B, C, D, and E and ask A whether they are all knights. If the answer is "yes," then F, G, H, I, and J are the knaves. So you MAY be able to identify all the knaves with just two questions. So the answer to your question as I understand it is 2. In any case, you will be able to determine the truth value of any further answer from A.

    But perhaps your question is what is the minimum number of questions that are guaranteed to classify correctly every one as a knight or a knave.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jun 2016
    From
    USA
    Posts
    12

    Re: Knights - knaves puzzle

    But perhaps your question is what is the minimum number of questions that are guaranteed to classify correctly every one as a knight or a knave.[/QUOTE]

    Yes. We want to precisely identify all 10 (which means that if we identify, say, the 5 knights, we are done).
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Jan 2009
    Posts
    343
    Thanks
    47

    Re: Knights - knaves puzzle

    I think I'm close to one question. There might be a hole. I'm not sure.
    JeffM's answer was good for putting me on the right track.

    Ask an inhabitant X: "If you were the opposite of who you were, (supposing knights and knaves are opposites) who out of the remaining 9 would you call a knave?"

    If X is a Knight: Has to tell the truth that, "supposing he were a knave, he would point to knights." Hence he'd point to 4 Knights.
    If X is a Knave: Has to lie about that "supposing he were a knight, he would point to knaves." Hence he'd point to the 5 Knights.

    Either way you know which are knights or knaves. If I'm wrong, I'm still convinced the crux of a one question answer would rely on a 4-5 person inequality.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Feb 2015
    From
    Ottawa Ontario
    Posts
    1,444
    Thanks
    272

    Re: Knights - knaves puzzle

    Is one plus one = two ?

    Worse case:
    yes's and no's tied after 8

    So 9.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Logic puzzle about knights and knave
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Mar 3rd 2015, 09:16 AM
  2. Knights of the Board
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: Apr 30th 2010, 09:39 AM
  3. [SOLVED] Knights and Knaves help >__<
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 30th 2009, 05:42 AM
  4. What road to take? Knights and Knaves puzzle.
    Posted in the Math Challenge Problems Forum
    Replies: 1
    Last Post: Jan 30th 2009, 12:26 PM
  5. Set Theory Knights Tour
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 20th 2006, 01:58 PM

/mathhelpforum @mathhelpforum