3
$\begingroup$

A basic knight-knave puzzle (for the purposes of this question) takes the form $Q(n, s, k, x)$, where:

$n$ men are guarding $n$ doors. The guards and doors are numbered for easy reference: Guard #1 guards Door #1, Guard #2 guards Door #2, and so on. $s$ doors leads to pots of gold (success), while the other $n-s$ lead to hungry lions (failure). The guards cannot move away from their assigned doors.

You know that $k$ guards always tell the truth (knights), and the other $n-k$ always lie (knaves).

You are allowed to ask $x$ questions in total - either interrogative or imperative. The questions do not have to be yes-no questions, and asking the same guard more than one question is permissible.

Singulars are corrected into plurals where applicable (e.g. asking a knight "point to the knave" when $n-k>1$, which gets treated as "point to all the knaves"), and vice versa.

A question can have no answer (e.g. asking a knight "point to a knight who isn't yourself" when $k=1$), multiple answers (e.g. asking a knave "who is the knight?" and getting a list of all knaves), or cause the guard to respond "KABOOM!" for logical paradoxes (e.g. asking a guard "if this sentence is true, does Germany border China?").

Under this notation, the classic case - 2 doors, 1 success, 1 knight, 1 knave, 1 question, "If I ask the other guard which door leads to the pot of gold, what would he say?" - would be $Q(2, 1, 1, 1)$.

(Some versions of the problem have guards present additional information, e.g. "Guard #1 says that Guard #2 is a knave", or introduce "spies" who always answer randomly, etc., but these aspects are not considered relevant for the purposes of this question.)

What conditions must $n, s, k, x$ follow for a knight-knave puzzle $Q(n, s, k, x)$ to be possible, and impossible?

Trivially:

  • $n > s, k$
  • $n, s, x > 0$

But what else?

Bonus questions:

  • What if you were only allowed to ask yes-no questions (in which case the 4 possible outputs are "yes", "no", "(none)", and "KABOOM!" for logical paradoxes).
  • What if there was a limit $c$ (where $c<x$) on how many times you could ask the same guard a question?
  • If there are cases where a 100% guarantee is not possible and you are forced to make random guesses, are there at least optimal strategies to maximize your luck?
  • Would allowing guards to move away from doors or exchange doors with each other change the outcome of these knight-knave puzzles in some mind-screwy way I haven't thought of?
  • What if we extend the premise to cases where $m$ men guard $n$ doors, and $m≠n$?
  • What if the guards and doors were impossible to identify and distinguish? (Like, say the room is circular and you're riding a carousel, and the carousel spins really fast between questions, making you dizzy?)
  • What if $n$, $s$, $k$, and/or $x$ were countably infinite?
Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ I think there might be a bit too many bonus questions here $\endgroup$
    – kagami
    Commented Jun 18 at 17:42
  • $\begingroup$ This is undetermined about what counts as a lie or the truth. I'd propose that (1) each question must have a finite set of possible answers, and (2) a liar may pick any answer from the set which he does not know to be the case, and (3) a truth-teller must know that exactly one of the answers is the case, and which answer it is, and will say that answer, and (4) if the truth-teller does not know that exactly one of the answers is the case, and which answer it is, the truth-teller instead immediately executes you $\endgroup$
    – causative
    Commented Jun 19 at 2:11
  • $\begingroup$ And (5) no one can predict which answer a liar will give if the liar has more than one option. Also just for completeness, (6) if the liar knows that all the answers are the case (and thus cannot answer), the liar instead executes you. $\endgroup$
    – causative
    Commented Jun 19 at 2:11

1 Answer 1

Reset to default
3
$\begingroup$

Sort of depends on exactly what a lie is, but here's a go.

I ask the question to the leftmost guard:

For an even number of liars: "If I were to ask the next guard the following question, what is a door he might indicate? That question is: if I were to ask the next guard the following question, what is a door he might indicate? That question is ... "which is the lowest number safe door?"

Where the ellipses represent enough layers such that the final part is directed to the final guard. For an odd number of liars, I can end with "which is an unsafe door."

This should result in the indication of a safe door. This works for all $n,s,x>0$.

For the yes-no version,

The final part is instead "is the value of the ones digit of the binary representation of the lowest safe door when numbered left to right equal to 1" and increase the digit x times (i.e. ones to twos to fours to eights and so forth). Again, you keep in mind that the result is flipped if there are odd liars. This should be optimal from an information theoretic standpoint unless we can take advantage of the non-yes/no options.

This general approach can be used as is or tweaked very slightly for most of the bonus questions. For the countably infinite one,

I can ask the original question, but instead of going down the line, it's directed from guard #1 to #2 to #3 to #1 to #2 to #3. There's necessarily an even number of liars in that list, so I'm guaranteed a safe door.

Improve this answer
$\endgroup$
7
  • $\begingroup$ This certainly doesn't work for 3 doors if guard 1 is a liar, guard 2 tells the truth, guard 3 is a liar, where door 1 has the gold and you ask your question to guard 1. Guard 3 has many options for "which doors are safe to open?" He could say doors 2 and 3. He could say doors 1 and 3. He could say doors 1 and 2. He could say just door 2. All of these are lies. And guard 2 doesn't know which of the lies guard 2 would say, so guard 2 cannot answer. So guard 1 can give any answer he likes and it would be a lie. $\endgroup$
    – causative
    Commented Jun 19 at 2:02
  • $\begingroup$ Adjusted such that a looser definition of "lie" still works. $\endgroup$
    – kagami
    Commented Jun 19 at 3:18
  • $\begingroup$ I think that fixes it. Only way I can think of to break it is if some of the guards have strict preferences, known to the other guards, that e.g. they will always answer door 3 if it is an available answer for them. $\endgroup$
    – causative
    Commented Jun 19 at 3:27
  • $\begingroup$ I honestly regret putting the countably infinite one. I did it as a whim and it's so poorly defined. $\endgroup$
    – Josh
    Commented Jun 19 at 5:39
  • $\begingroup$ @causative in my formulation of the problem, if Door #1 is the only safe door out of the 3, and you ask Guard #3 (a liar) to name the safe door(s), he will name all the unsafe doors in response: #2 and #3. $\endgroup$
    – Josh
    Commented Jun 19 at 5:44

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