7
$\begingroup$

There are 3 types of inhabitants of a village: knight, knaves, normal. You should map each inhabitant with its type, by asking only this type of question to a person: "Hey X, what is the type of person Y". Knights will answer the correct type of Y, knaves will answer anything but the actual type of Y, and normal people will be able to answer simply any type.

Constraints: - Everyone know the exact type of any person in the village.

  • You can only ask the question defined above.

  • X can not be the same as Y. Means, you cant ask a person the type of himself.

  • If you already asked a person and it already have its answer, it wont change its answer if you asked the same question again and again

  • More than the half of the village inhabitants are knights

  • No limit on the number of questions asked

I was meant to solve this problem with an algorithm, and efficiency is not the main concern.

I can understand the original knight, knaves, and spies puzzle, or the famous THLPE puzzle, but given the limitation of the question allowed (as stated above), and extra information of amount of knights (as stated above), how can I solve this puzzle? Thanks!

Improve this question
$\endgroup$
1

4 Answers 4

Reset to default
11
$\begingroup$

If efficiency is not a problem:

Ask everyone what everyone else's type is. Since the majority is Knights, the majority answer will be correct for every person in the village. If it's an even split, the person is a Knight, making the total number of Knights 50%+1.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Nit: "If efficiency is not a concern" or "if inefficiency is not a problem" $\endgroup$
    – ikegami
    Commented Oct 6, 2019 at 18:39
  • $\begingroup$ Simple, clear, obviously correct. $\endgroup$
    – user3294068
    Commented Oct 8, 2019 at 13:59
6
$\begingroup$

An improvement on Braegh's answer.

  1. Ask everyone what Y1's identity is. Majority is correct. If Y1 is a villager or a knave, repeat this step. Otherwise, proceed to step two.

  2. Use the knight to determine everyone else's identity.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ If Y1 is a villager or a knave, some in the majority can be villagers, so you would have to repeat with others from that majority until you find a knight. Still takes off half the time in a worst case scenario, I believe? $\endgroup$
    – Braegh
    Commented Oct 5, 2019 at 19:16
  • 1
    $\begingroup$ This does not work as a normal person could give the correct answer to $Y_1$'s type. You cannot then just choose someone who is in the majority because you might get a normal. You could then choose $Y_2$ and ask all the people in the majority what type $Y_2$ is, and keep going until one of the people you ask about is a knight. $\endgroup$
    – Ross Millikan
    Commented Oct 6, 2019 at 0:05
  • $\begingroup$ @RossMillikan and Braegh - ah, fixing $\endgroup$
    – Brandon_J
    Commented Oct 6, 2019 at 0:58
3
$\begingroup$

If the population size is N, then you need at most 2N questions.

  1. It suffices to find one knight using at most N questions.

  2. When person A says that person B is not a knight, then at least one of A and B is not a knight.

  3. Number inhabitants from 1 to N. Let m=1 and repeat the following steps. a) If m>N/2, then the m-th person is a knight. b) Otherwise ask the m-th person whether the (m+1)-th person is a knight. c) If yes, increase m by 1 and go to (a). d) If no, remove the m-th and (m+1)-th persons from consideration, relabel the persons m+2,...,N by m,...,N-2, decrease m by 1 (unless m=1), decrease N by 2, and go to a). Exercise: show that this algorithm terminates after at most N steps and yields a knight.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I think the algorithm terminates in at most N/2 steps, so your solution is more efficient than you give yourself credit for. $\endgroup$
    – user3294068
    Commented Oct 8, 2019 at 14:35
  • $\begingroup$ Here's my thoughts for how to prove your algorithm: Because we have majority knights, we know that as we proceed we will always talk to a knight at or before person m>N/2. If anyone is removed before then, it is either two non-knights, or a non-knight and a knight, but in either case the majority are still knights. Once we talk to a knight, either we reach m>N/2 entirely via knights, or we start removing knight+non-knight pairs, again still majority knights. If we run out of talked-to-knights, because majority knights we'll talk to another knight before we get to m>N/2. $\endgroup$
    – Rob Watts
    Commented Oct 28, 2019 at 22:27
0
$\begingroup$

Further efficiency:

Pick one person A from among the people who have never been picked, or been asked a question.

Start asking other inhabitants (chosen from those who have never been picked or asked a question) if A is a knight until either more inhabitants have answered No than Yes, or until the number of Yes answers equals the number of No answers plus the number of unasked people.

In the first case, go back to step 1. In the second case, A is a knight, and you can get the rest of the information by asking A questions.

(In any round of 1 & 2, if A was a knight, then everybody who said No was not a knight. If A was not a knight, then A and everybody who said Yes was not a knight. In any case, you're excluding at least as many non-knights as knights from future rounds, so the unasked people is majority knight.)

Total questions is about three times the population.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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