6
$\begingroup$

I found somewhere this 'knights and knaves' problem (I can't locate the source anymore):

An Island is inhabited by exactly $n$ people, with $n>2$, of whom some (the exact number is not known) are knights, who alwais tell the truth, and some are knaves (the exact number is not known, but it is known that there is at least 1 knave). Every knave always lies, except for one of them (exactly one), their boss, who always tells the truth. An explorer arrives to this Island, and he knows all the information reported in the text of this problem, the name of all the inhabitants of the island, and nothing else. He can ask any number of question to anyone, but every question must be of the kind "Is X a knight or a knave?". What is the least integer number $m$ so that the explorer has a strategy to be certain of guessing correctly who is the knaves' boss with no more than $m$ questions?

I showed that $m\le n$ if $n$ is even and $m\le n+1$ if $n$ is odd by the following simple argument: let $1,2,\dots n$ be the names of the islanders, one proceeds asking to 1 about 2 and viceversa; if both answer the same none of them is the knaves' boss, otherwise one of them is. So by doing this trick with couples $2k-1,2k$ for $k=1,2,\dots \lceil n/2\rceil-1$, we have surely found a group of 2 people at most of whom one is the knaves' boss. WLOG, let's assume he is one of 1 and 2. Now ask 1 about 3 and viceversa, and you will be able to guess with certainty who the boss is. This procedure leads to the $n$ / $n+1$ upper bound on $m$. But I can't find any way to try showing this is indeed the minimum (or find a better procedure). I'd be very glad if someone may help me on this.

$\endgroup$
  • $\begingroup$ Hmm. If you do it in trios rather than pairs three without the boss will answer either 3 knights or 2knaves and 1 knight. But a trio with the boss will be either 2 knights and 1 knave or 3 knaves. So that can get it in rough n/3. $\endgroup$ – fleablood Apr 16 '18 at 17:36
  • $\begingroup$ Well, each question only gives you information on 1 person. So fewer than $n-1$ questions will give you at least two people with no info. So $n-1$ is the minimum. $\endgroup$ – fleablood Apr 16 '18 at 17:47
  • $\begingroup$ @fleablood the problem there is that 'doing' a trio requires three questions; your argument make a rough estimate of n/3 trios that again is about n questions $\endgroup$ – L. Bresolin Apr 16 '18 at 17:58
  • $\begingroup$ @fleablood well I'm not interely sure that each question give information about a single person (one can peraphs extract some info about both the person you ask to and the person you ask about); I totally agree that it must be $m>n/2-1$ (and that is clearly a rather bad lower bound) but this doesn't in fact esclude $m<n-1$. $\endgroup$ – L. Bresolin Apr 16 '18 at 18:08
  • $\begingroup$ Yeah, I thought you were doing something about the number of pairs and a minimum of n(n+1)2 pairs and if you did it in triplets... but that wouldn't make any immediate difference (and makes things worse later). $\endgroup$ – fleablood Apr 16 '18 at 18:17
2
$\begingroup$

You can ask $X$ a question "Is $X$ a knave?". Only the knave boss will answer "Yes" for this question, thus there is possibility to ask $n-1$ questions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.