You are not logged in.
Pages: 1
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?
Offline
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?
Knights always tell the truth, knaves always lie. Ask them a fact question. => Do you live on an Island?
Knights will always tell the truth, hence, they will all say yes.
Knaves always lie, hence, they will all say no.
The minimum number of yes-no questions that he must ask the inhabitants is 9. (5-yes 4-no/ 5-no 4-yes) At 9, there's enough information to find out the 5 naves.
His dominion is an everlasting dominion, Which shall not pass away, And His kingdom the one Which shall not be destroyed.
Offline
I believe it can be done with 8... I cannot prove it though.
samuel.bradley.99 wrote: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?Knights always tell the truth, knaves always lie. Ask them a fact question. => Do you live on an Island?
Knights will always tell the truth, hence, they will all say yes.
Knaves always lie, hence, they will all say no.The minimum number of yes-no questions that he must ask the inhabitants is 9. (5-yes 4-no/ 5-no 4-yes) At 9, there's enough information to find out the 5 naves.
Offline
The minimum number of yes-no questions that he must ask the inhabitants is 9. (5-yes 4-no/ 5-no 4-yes) At 9, there's enough information to find out the 5 naves.
To be precise,
The minimumof minimum number of yes-no questions that he must ask the inhabitants is 5.
The maximumof minimum number of yes-no questions that he must ask the inhabitants is 9.
{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}
Offline
David wrote:The minimum number of yes-no questions that he must ask the inhabitants is 9. (5-yes 4-no/ 5-no 4-yes) At 9, there's enough information to find out the 5 naves.
To be precise,
The minimumof minimum number of yes-no questions that he must ask the inhabitants is 5.
The maximumof minimum number of yes-no questions that he must ask the inhabitants is 9.
But the question doesn't specify.
His dominion is an everlasting dominion, Which shall not pass away, And His kingdom the one Which shall not be destroyed.
Offline
Can you ask the same person more than once?
{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}
Offline
Can you ask the same person more than once?
Exactly, I was thinking about that.
His dominion is an everlasting dominion, Which shall not pass away, And His kingdom the one Which shall not be destroyed.
Offline
Can you ask the same person more than once?
I believe yes.
Offline
What if we start with all possible ways to pick 5 persons out of 10, which are 10!/5!*5!=252, then ask one question to one of the inhabitants (the question that David specified, or any other with an obvious answer) so as to identify one knight or knave. Then we will have 9 remaining inhabitants with 5 knights and 4 knaves or the opposite. Then all possible ways to select 4 (or 5) out of 9 will be 9!/4!*5! = 126. Since 126<128=2^8, can we deduce that this can be covered by 7 questions (since, to cover 128 possibilities we need 8 questions) plus the first one. That gives 8 questions in total. Is this correct?
Can anyone work out an example?
Offline
What I would suggest is ask David's question to one person.You would come to know whether he is knight or knave. then you ask him to list who are the knights.Two questions are enough.
{1}Vasudhaiva Kutumakam.{The whole Universe is a family.}
(2)Yatra naaryasthu poojyanthe Ramanthe tatra Devataha
{Gods rejoice at those places where ladies are respected.}
Offline
What I would suggest is ask David's question to one person.You would come to know whether he is knight or knave. then you ask him to list who are the knights.Two questions are enough.
Wow. Nice
His dominion is an everlasting dominion, Which shall not pass away, And His kingdom the one Which shall not be destroyed.
Offline
What I would suggest is ask David's question to one person.You would come to know whether he is knight or knave. then you ask him to list who are the knights.Two questions are enough.
All questions must be answered by yes or no.
Offline
Pages: 1