Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2016-12-06 23:43:33

samuel.bradley.99
Member
Registered: 2016-03-16
Posts: 51

Knights and knaves

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

#2 2016-12-07 12:48:30

David
Member
From: Bumpkinland
Registered: 2014-04-23
Posts: 3,135

Re: Knights and knaves

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.


Meaningless, meaningless, Everything is meaningless! - Ecclesiastes 1:2

Offline

#3 2016-12-07 20:41:41

samuel.bradley.99
Member
Registered: 2016-03-16
Posts: 51

Re: Knights and knaves

I believe it can be done with 8... I cannot prove it though.

David wrote:
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

#4 2016-12-07 21:20:19

thickhead
Member
Registered: 2016-04-16
Posts: 1,086

Re: Knights and knaves

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.


{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

#5 2016-12-07 21:30:02

David
Member
From: Bumpkinland
Registered: 2014-04-23
Posts: 3,135

Re: Knights and knaves

thickhead wrote:
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.


Meaningless, meaningless, Everything is meaningless! - Ecclesiastes 1:2

Offline

#6 2016-12-07 21:32:51

thickhead
Member
Registered: 2016-04-16
Posts: 1,086

Re: Knights and knaves

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

#7 2016-12-07 22:58:58

David
Member
From: Bumpkinland
Registered: 2014-04-23
Posts: 3,135

Re: Knights and knaves

thickhead wrote:

Can you ask the same person more than once?

Exactly, I was thinking about that.


Meaningless, meaningless, Everything is meaningless! - Ecclesiastes 1:2

Offline

#8 2016-12-08 00:08:32

samuel.bradley.99
Member
Registered: 2016-03-16
Posts: 51

Re: Knights and knaves

thickhead wrote:

Can you ask the same person more than once?


I believe yes.

Offline

#9 2016-12-08 00:20:00

samuel.bradley.99
Member
Registered: 2016-03-16
Posts: 51

Re: Knights and knaves

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

#10 2016-12-08 21:11:34

thickhead
Member
Registered: 2016-04-16
Posts: 1,086

Re: Knights and knaves

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

#11 2016-12-08 23:45:50

David
Member
From: Bumpkinland
Registered: 2014-04-23
Posts: 3,135

Re: Knights and knaves

thickhead wrote:

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


Meaningless, meaningless, Everything is meaningless! - Ecclesiastes 1:2

Offline

#12 2016-12-09 07:58:45

samuel.bradley.99
Member
Registered: 2016-03-16
Posts: 51

Re: Knights and knaves

thickhead wrote:

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

Board footer

Powered by FluxBB