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

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

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

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

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

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

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

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

David wrote:

samuel.bradley.99 wrote:

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

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

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 **minimum**of minimum number of yes-no questions that he must ask the inhabitants is 5.

The **maximum**of 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****Member**- From: Bumpkinland
- Registered: 2014-04-23
- Posts: 3,135

thickhead wrote:

David wrote:To be precise,

Theminimumof minimum number of yes-no questions that he must ask the inhabitants is 5.

Themaximumof 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

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

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

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

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

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

thickhead wrote:

Can you ask the same person more than once?

I believe yes.

Offline

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

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

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

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

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

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

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

thickhead wrote:

All questions must be answered by yes or no.

Offline

Pages: **1**