# A knights and knaves problem with one truth-saying knave; what is the minimum number of questions needed to find this atypical knave?

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.

• 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. Apr 16, 2018 at 17:36
• 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. Apr 16, 2018 at 17:47
• @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 Apr 16, 2018 at 17:58
• @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$. Apr 16, 2018 at 18:08
• 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). Apr 16, 2018 at 18:17

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.
Jaroslaw showed that $$n-1$$ questions suffice.
To show that many are necessary, consider the possibility that the knave's boss is the only knave. Asking A about B will reveal whether or not B is the boss. Worst case, you don't ask anybody about the knave's boss until you've asked a question about every other person, which will take $$n-1$$ questions.