Find the identity of the four troll brothers

Question

The four troll brothers Wudhor, Xhaqan, Yijlob and Zrowag have the following properties:

• Wudhor always says the truth.
• Xhaqan always lies.
• Yijlob lies or says the truth unpredictably.
• Zrowag is deaf and never answers.

You are brought in front of the four trolls you haven't seen before and must ask questions to determine who is who. You may ask each troll as many times as you want but only yes/no questions. The trolls may kill you if you ask them a question they don't know the answer, so be careful.

How many questions do you need to ask at a minimum, and in the worst case, to be sure to determine who of the trolls is who? (Each time you ask something it counts as a question, even if it's the same question and the same brother)

Answer 1

The mathematically minimum possible solution is:

Four questions.

Credit to supercat and user1540815! I overlooked an important fact in my first draft.

If the trolls stand in one line, there are 4 possible identities for the first troll, 3 for the second, 2 for the last. Overall, this is 24 possible combinations.

Trolls: W (truth),X (liar),Y (random),Z (mute)

Any question to Zrowag (mute troll) will give you only one piece of information: he is the deaf one. This will reduce your pool to 6 combinations for the other 3 trolls.

Each further question is a strict yes/no question, without any tricks. This will get you at most 1 bit of information. So whatever clever question you design, the next question will at most half it to 3 combinations. Next question will half it to 2 combinations and the fourth and last question will decide it.

How does it work if I ask a Troll first who isn't Z ? I get more than 1 bit of information for any question to a new troll before I know who Z is. If I get an answer, I will also know that The troll I asked is not Zrowag and can at best half the remaining possible combinations.

So if I ask the first troll and he does answer, I will reduce the possible combinations from 24 to 18 (because there are 6 combinations where Zrowag is the first troll) and then can half the remaining space to 9.

The second question needs to be asked to a different troll, so I will either find Zrowag to reduce the combination-space to at most 3 possible combinations ( since with a good question my 9 combinations left after the first question will be 3 for each possible position of Z)

If the second Troll also is not Zrowag, my second question will again eliminate 3 combinations (because I know Zrowag is not on place 2) leaving 6 combinations, which my yes/no question can again split in half to 3 possible combinations.

If I get lucky I now only need one more question, since my 3 combinations will be two combinations with Zrowag in Place 3 and one with Zrowag in place 4, So if I ask the troll in place 3 and he is Zrowag I'm done, otherwise my question can split it again to the last remaining option and done.

So if I get lucky I can get it in 3 Questions, but worst-case still remains 4 Questions.

Example Questions to get it in Four:

I will arbitrarily number the 4 Troll 1-4 for the Place they are standing in (assume they stand in a line)

First I will try to find a Troll who is either W or X (either tells the Truth or lies)

Question 1: Ask Troll 1:

From the trolls who can speak, is the Troll closer to you more likely to lie?

Scenario 1a: I ask W (truth teller). He has to decide which one of X(liar) and Y(random) is more likely to lie. He will say "yes" if X is closer to him and "no" if Y is closer. If he answers "yes", I will ask the closest troll to him next. If he answers no I will ask the furthest troll next. - So I will ask Z or X next.

Scenario 1b: I ask X(liar). If W(truth) is closer to him, he will lie and say "yes". If Y(random) is closer he will say "no". By choosing the same as in 1a I will ask Z or W next.

Scenario 1c: I ask Y(random). He will randomly say "yes" or "no" so I will choose W,X or Z next.

Scenario 1d: I ask Z(mute). He will not respond, I know who Z is and ask the same question to Troll 2. This will cost me one question, but I know who Z is and will continue and need 3 more questions overall.

Question 2: Ask Troll 2 or 4 (where we know he is NOT Y(random))

Can you hear me?

Scenario 2a: Yes! He is W(truth).

Scenario 2b: No! He is X(liar)

Scenario 2c: He remains silent. He is Z(mute) - I will ask the same Question to the next troll in line and will have used one Question for Zrowag.

Question 3: Ask the Troll again (I know he is W or X so I know if he will tell the truth)

Is this Yijlob? (pointing to the first Troll who spoke)

Scenario 3a: He confirms it (Either W saying yes or X saying no) I know who Yijlob is. The remaining two must be the opposite of the current troll and Zrowag

Scenario 3b: He denies it. (Either W saying no or X saying yes) I know the first one is now the opposite of my current Troll (either W or X) and the remaining two others must be Yijlob and Zrowag

If I already know who Zrowag is, I am done now (and used 4 Questions)

Question 4: Ask the Troll again if you have not found Zrowag yet

Is this Zrowag? (pointing to one of the two remaining Trolls)

I now have sorted out the last two troll and am done.

Daredevils may only need 3 questions

Since our goal is only to know who each troll is, the riddle doesn't mention we need to survive with this knowledge for long. Using the option of asking a question which a troll cannot answer, we have a third outcome to a question: The troll may kill us (even if he does not, X and W can only lie and tell the truth, so are not able to answer certain questions) Since we may die, we can only use this on the last question. Since we can theoretically always get down to 3 possible permutations with 2 question, the third question could divide them into yes/no/die and in the worst case we would know the solution when the troll kills us.

I would love if someone finds actual questions to solve this in three, although it is probably stretching the rules of the riddle. - the proposed solution for 4 questions is not optimal and will leave us with 10 permutations after the first questions and get only to 4 after the second question. But it could be possible with better questions.

Answer 2

Assuming trolls know one another, here's a solution for

Five

Follow:

STEP 1 - Ask "ARE YOU YILJOB?" to everyone.

 CASE 1: YILJOB LIES
 Answers: No Yes No x
 Identified Zrowag and Xhaqan
  STEP 2- Pick one of the unidentified randomly and ask "IS THIS WUDHOR?" to Xhagan.
  He lies all the time so, identify the troll accordingly.
  Identified everyone.
 In total 5 questions.

 CASE 2: YILJOB TELLS THE TRUTH
 Answers: No Yes Yes x
 (Note that we can distinguish this from case 1 by counting "yes" and "no" answers.)
 Identified Zrowag and Wudhor
  STEP 2- Pick one of the unidentified randomly and ask "IS THIS XHAGAN?" to Wudhor.
  He is honest all the time so identify accordingly.
  Identified everyone.
 In total 5 questions.

Answer 3

I believe four works. Figure that at some point one will ask Zrowag a question and get no response, so that burns a question but the only relevant permutations are the six involving the other brothers.

Start by asking #1 if the next brother who can speak is less prone to telling the truth than the last brother who can speak. An affirmative answer will imply that the next brother who can speak will be W or X (the brothers will either be YWX, YXW, WXY, or XWY). A negative answer will imply that the last brother who can speak is W or X (YWX, YXW, WYX, or XYW).

After identifying someone who must be X or W, ask that brother something to which the truthful answer would be yes. That will indicate whether that brother is X or W. Finally, ask that same brother if the first brother is Y (inverting the response if talking to X).

Answer 4

I can do it in

five questions.

First

ask all of them a question to which everyone knows the answer. ("Is 1=1?") You will get the truth from W, a lie from X, something from Y, and silence from Z.

At this point

you know which one is Z, and you have identified either W or X, whichever was the odd one out among the other three.

Now

one further question to the odd one out ("is this one Y?") will tell you everything.

Note: This is closely related to smriti's solution but fixes an error in it; but Sora's answer gets the result with the same number of questions in a similar way and was posted before mine. I think this solution is slightly simpler but Sora got there first and should get the checkmark if (1) the thing can't be done in fewer questions and (2) a minimal solution without a minimality proof is acceptable at all :-).

Answer 5

An answer to another question indicates how to tell who's who in a slightly similar situation: three people, each is like W, like X, or like Y, there is at most one Y-type (but the other two might both be W-like or both be X-like).

This solves that problem in six questions, which can be decided in advance and don't need to adapt to the answers actually given. (There are no questions like "What would so-and-so say if ...?" which might get you killed if they refer to Y.)

We can apply that to the present situation. Ask the brothers any yes/no question (e.g., "Are you W?") one by one until one fails to answer or you've asked three of them. Now you have asked <= 3 questions and know which one is Z. Now apply the 6-question procedure to the other three.

This gives a solution in at most nine questions.

I haven't spoilered it because (1) most of the details are at the far end of a link and (2) I would be astonished if this were the best possible.

Answer 6

Minimum of 3 questions in the best case (not 4):

Ask B if A is Zrowag. He answers “No.”

Ask C if A is Zrowag. He answers “No.”

Ask D if C is Yiljab. He answers “Yes.”

======================================

Because B, C, D all answered, A -> Zrowag.

Because B/C answered questions with lies, B/C -> Xhaqan/Yiljab AND D -> Wudhor

Because Wudhor said C is Yiljab, C -> Yiljab; B -> Xhaqan

======================================

Also, to nitpick Falco's answer about worst-case scenario (this would be a comment if I had enough rep):

1.) Agreed, you are down to 6 possible permutations. A-> Zrowag

2.) Slightly incorrect. You know if he answers "Does 1+1=2" with "Yes" that he is NOT the liar, and if he answers "No" that he is not the truthteller. You've gained information in either case, although it is not enough to deduce the identity of any trolls directly

3.) (Assume without loss of generality that B said “yes”: B->Yiljab or Wudhor) Since I know he cannot be the liar, I ask C: “Is the person who just answered Xhaqan?”

Consider what happens if C says no: B/C -> Yiljab/Wudhor since both told the truth, and I can wrap up with one question

4.) Ask D->Zrowaq “Is the person who just answered Wudhor?”. 4 Questions total to uniquely identify each, after getting Zrowag/Yiljab as my first 2 responders.

To be clear, I do believe you found the correct lower bound, and I liked the attempt at a rigorous mathematical proof, but I think the logic needs to be cleaned up slightly. You do gain information with each question if you ask them correctly, just not enough to identify a troll per question.

Handwaving away the information gained in question 2 oversimplifies your final analysis (With perfect luck and the right questions you could finish up in 2 additional questions).

=======================================

Since there are 6 combinations after step 1 (not 8), it is not required to get a full 3 bits of information to distinguish between them. After getting a fractional bit from question 2, the possibilities are either:

Truthful answer to question 2: WXY or WYX or YWX or YXW

Lying answer to question 2: XYW or XWY or YWX or YXW

As you can see the problem has in fact been reduced to 4 possibilities by the second question in your worst case scenario, which can absolutely be solved by 2 questions getting 1 bit of information each.

Answer 7

These type of questions seriously give me headache! But here is my solution :
First

Ask each of them the same question : 'is 1+1=2?' W will say 'yes'; X will say'No'; Y will say something randomly ; and Z wont speak.

So,

we know, that X is liar and Z is deaf.

Now,

Ask X "will person next to you have more probability to give correct answer than person behind you?" If he says no; then person next to him is truth-teller ie. W; and remaining one is randomizer Y

Answer 8

All the answers so far deal with the worst case scenario. For the best case scenario you can do it in

4

By

Asking each demon is 1+1=2 if you receive answers
yes, yes, no you now know the last demon is Zrowag so you don't need to ask him a question, you also know Xhaqan as the only one that lied
yes, no, no you now know the last demon is Zrowag so you don't need to ask him a question, you also know Wudhor as the only one that told the truth
yes,yes,x you know the one who hasn't answered is Xhaqan and you know Zrowag
no,no,x you know the one who hasn't answered is Wudhor and you know Zrowag
For the last question either ask Xhaqan or Wudhor (whichever one you have identified) "Is this Yijlob" which will identify the last two demons

yes,no,x is the last case you can get and in this case you need the full 5 questions as others have stated.

Answer 9

I can do it in 2 (with a lateral approach)

"I address this question to all four of you, is Zworag deaf" Zworag will not answer and you can determine that if there is only one yes >that is from Wudhor or if only one no it's from Xhagan ! !If you know who Wudhor is, you ask Wudhor if one of the two unidentified is Yijlob.

Alternatively if you know who Xhagan is you ask Wudhor if one of the two unidentified is Yijlob and know that his answer will be a lie.

Of course this does rely on the assumption you can address a single question to all four trolls and count it as one.

I think that other answers better get the intent of the question, but I thought this was worth adding anyway.

Answer 10

It can be done with four questions.

The names of the trolls made my head hurt, so I changed the problem to the traditional knight (always says the truth), knave (always lies), spy (says the truth or lies as he pleases), and we have one who is mute (gives no answer). Determining their order with four questions is tough and some think it is impossible. But to our advantage there are not two possible answers but three - yes, no, and silence. So if we ask a question and get no answer, the possibilities go down from 24 to 6 because we know who is the mute. And if we don't know it yet at that point, then the third question will always tell us who is the mute.

I'll use a tool that I call "truth-asking". If I ask a question X, I never know if the answer is the truth or not. "Truth-asking the question X" means asking the question "is it the case that either you are the knight and X is true, or you are the knave and X is false"? Both the knight and the knave will say "yes" if X is true and "no" if X is false. The spy might say yes or no. So looking at the possible answers: If we truth-ask the question X, then no answer means we asked the mute. "Yes" means either we asked the spy, or X is true, or both. "No" means either we asked the spy, or X is false, or both. If we know that the person we ask is not the spy, then we get either no answer (and the person asked is the mute), or we get the true answer to our question.

If the mute wasn't there, we could easily find everyone's identity in three questions (3-person problem). Call the three people A, B and C. We truth-ask A: Is C the spy? If the answer is yes, then either A or C is the spy, and B isn't. If the answer is no, then either A or B is the spy, and C isn't. We truth-ask the person who is not the spy whether A is the spy, and the answer reveals the identity of the spy. Then we truth-ask the same person if they are the knight, which reveals who is the knight and who is the knave.

Now the 4-person problem. We call the four people A, B, C and D.

We "truth-ask" A the question: Is B the knight or the knave, or is B the mute and C the knight or the knave? If we get no answer, then A is mute, and we are left with the 3-person problem which we solve in three more questions, so we can assume that A is not the mute and we get an answer.

If the answer is yes: Either A is the spy (and therefore B, C and D are knight, knave and mute), or A is a knight or knave, and either B is another knight or knave, or B is mute and C is another knight or knave. Anyway, B is not a spy! So we truth-ask B: Is A the spy? If we get an answer then we also truth-ask B: "Is A the knight" and "is C the spy", and the answers are all truthful so we know who is who. If B doesn't answer then B is mute and C is a knight or knave, so we truth-ask C the questions: "Is A the spy" and "is C the knight" and the truthful answers tell us everything.

If the answer is no: Either A is the spy (and therefore B, C and D are knight, knave or mute), or A is a knave or knight, and either C is the knight or knave, or C is mute and D is the knight or knave. So we have the exact same situation as with the answer "yes", but with C and D instead of B and C, and can again solve the problem with four questions.

Altogether: We can solve this in four questions.

Answer 11

Assuming you can ask questions about yourself because they all can see you, you can ask basic questions like your own hair color(brown) this will eliminate the aspect of them not knowing the question

You ask is my hair color brown?

Amount of questions: 1

if you get an answer of :

• yes no yes x:
  after that you only ask Wudhor and Yijlob the same question over and over until it is different from one another and you have identified all

• yes no no x:
  then repeat with Xhaqan and Yijlob

Answer 12

This answer is Incorrect I have left it here so others may avoid the same.

We can do it in

4 questions
Note: I now believe it is not possible in less than 5

By

First asking 3 of them "Are you Yijlob?"

case A.
one of them does not answer - he is Zrowag
The two spoken answers would then break down as (A1), (A2) or (A3):
A1. Yes Yes
- the fourth is Wudhor, ask him "is this Yijlob?" regarding one of the unidentified brothers, he will tell us the truth which tells us the remaining two identites;
A2. Yes, No (in some order)
- one of these two is Yijlob, ask the fourth "If I asked a brother from these two who is not Yijlob the same yes/no question twice, is it possible that I could get different answers?" regarding the two who spoke.
A2a. Yes
- the fourth is Xhaqan, the one who spoke previously with a "Yes" is Yijlob and the one who spoke previously with a "No" is Wudhor;
A2b. No
- the fourth is Wudhor the one who spoke previously with a "Yes" is Xhaqan and the one who spoke previously with a "No" is Yijlob
A3. No, No
- the fourth is Xhaqanr, ask him "is this Yijlob?" regarding one of the unidentified brothers, he will tell us a lie which tells us the remaining two identites;

case B.
they all answer, the fourth is Zrowag
It is not possible that all three answered the same (we have either YYN or YNN in some order), the one who answered differently to the other two cannot be Yijlob, so if that one said "Yes" he is Xhaqan and if he said "No" he is Wudhor. As in (A1) and (A3) we can identify the remaining two with a single question.

Answer 13

It can actually be done in

four questions.

You need at least that many because

if your first question goes to Zrowag there are six possibilities left, and you can only get one bit of new information from each further question.

Here is a strategy which achieves this.

We aim to establish, after two questions, which troll is Zworag and that a particular troll is either Wudhor or Xhaqan. Once we have done this we can win, since there are four possibilities left and from a troll known to be W or X we can get a truthful answer to any question by asking "If I asked you [question], would you say yes?"
Ask the troll on your left "Of your non-deaf brothers, is the more truthful one further to my left?" If he answers "Yes", then of the two other non-deaf trolls, the one to the right is W or X. This is because if you asked W then he truthfully said that Y is further left than X, if you asked X then he lied, so Y is further left than W, and if you asked Y then the remaining non-deaf trolls are W and X in some order. Similarly, if he answers "No", then of the two other non-deaf trolls the one to the left is W or X.
If you got an answer, assume without loss of generality that it was "Yes". (The other case is the same with the remaining trolls rearranged.) Point at one of the middle two trolls and ask the rightmost troll "If I asked you if he was Zworag, would you say yes?" If you get no answer, the troll you just asked is Z and the second troll from the right is W or X, so we're done. If you get an answer you now know which troll is Z and that the troll you just asked is W or X, so again we're done.
If you got no answer to the first question, the leftmost troll is Z; ask the same question to the next troll and you can establish one of the remaining two as being W or X, so done.

Answer 14

Actually, I think only one of the above answers got the minimum number of questions right. However I'd suggest a (maybe easier) way to get there.

My answer is the following:

The minimum number of questions is

three

Here is how you should go.

You ask the first two Trolls "Are you Zrowag?". In the following I'll use just the letters W (truth) X (lie) Y (could be both) and Z (deaf). Now to be able to do it with 3 questions, you need to have gotten an answer in both cases (which means none of them is Z).

Now there are three possible cases. In two of which you can finish with the minimal number of questions. Here is the first one:

You got 2 "Yes" this means the first two must be X and Y, since they both lied. You just need to determine who is who, so you ask the third Troll, which is either W or Z, "Is Troll Nr.1 X?". Here you again have to be lucky and get an answer (meaning the third Troll is W). Since he always tells the truth, you can trust him and know who out of the two Trolls that answered "Yes" on "Are you Z?" is X and who is Y. The one that has not been asked any questions so far is Z.

Second case:

You got two "No", this is basically the same as case one but now you know the first two Trolls are W and Y. Now you ask the third troll "Is Troll Number 1 W?" and again you have to be lucky and get an answer. This time however, you have to keep in mind that the answer is a lie, i.e. if the third Troll answers "Yes" you know Troll number 1 is not W but Y and vice versa. The fourth is again Z.

In those two cases (with quite a bit of luck involved since this does not only require the right ordering of Trolls but also depends on Y answering in your favour) you can do it in the minimum number of questions, however, in general you can always do it with

five questions

like this:

ask every Troll "Are you Z?" you either get one "Yes" and two "No" (and no answer from Z obviously), or two "Yes" and one "No". Adress the Troll whose answer was unique (not answering not being counted an answer) with the question "is this Y?" pointing at one of the Trolls who gave the same answer. Now depending on whether the Troll you asked said "Yes" on "Are you Z" (meaning he is X) or "No" (meaning he is W) you know whether his answer is true or false but in any case you can be sure to have all the identities.

Answer 15

Could it not be simple math?

Does 2+2=4?

Ask this to three brothers and you should be able to get it sussed I think.