48
$\begingroup$

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)

$\endgroup$
  • 7
    $\begingroup$ Do the trolls all know one another's identities? Are they able to make logical deductions? Can they handle hypothetical situations? (I ask because of the "may kill you" stipulation plus the fact that trolls in mythology and fantasy literature tend to be rather stupid.) $\endgroup$ – Gareth McCaughan Aug 22 '16 at 9:57
  • 1
    $\begingroup$ Yes, yes and yes. They're brothers and they are not that stupid as they tend to be depicted. $\endgroup$ – Lynn Aug 22 '16 at 10:02
  • 1
    $\begingroup$ And, just to clarify, if I ask A "what would B say if ...?" and B is actually Yijlob whose answer to the embedded question is unpredictable, then it is likely that A will kill me (rather than e.g. answering "I don't know" or giving an answer that itself is unpredictable)? $\endgroup$ – Gareth McCaughan Aug 22 '16 at 10:06
  • 1
    $\begingroup$ The trolls only answer yes/no questions. Not "What..." questions. So, yes, they will kill you if you ask. $\endgroup$ – Lynn Aug 22 '16 at 10:14
  • 5
    $\begingroup$ +1 I like this question because it disallows a lot of "What would X say if I asked him Y" questions by stating that the trolls will kill you if you ask a question they can't answer. Since one of them answers unpredictably, that kind of question becomes too dangerous, since they won't know how he will answer. $\endgroup$ – GentlePurpleRain Aug 22 '16 at 15:53

15 Answers 15

28
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I believe your reasoning is incorrect, although your result is correct. My reasoning is that in step do you do gain information (you reduce the possible combinations from 6 to 4 by either ruling out the second answerer as a liar, or ruling him out as a truth-teller). With 4 combinations left after 2 questions, it would be possible (getting 1 bit per question) to correctly identify the answer. I have a more complete explanation included in my answer (I didn't have enough rep to comment a few hours ago). I'd love to see this proof corrected, I love the information theoretic approach. $\endgroup$ – stevenjackson121 Aug 22 '16 at 19:36
  • 2
    $\begingroup$ I believe neither the reasoning nor result is correct, since a properly-designed first question will, if answered, identify someone who isn't Yijlob (if the first question is asked of Zrowag, the second question will identify someone who isn't Yijlob). $\endgroup$ – supercat Aug 22 '16 at 21:57
  • 1
    $\begingroup$ Perhaps I used the wrong word. The reasoning behind the answer is correct. The "Imagine this as worst case" scenario was incorrect. We did gain information with question 2 that would enable us (in at least some scenarios) to finish up in 4 questions. Steps 2-5 were oversimplified in the "Imagine this as worst case" scenario. $\endgroup$ – stevenjackson121 Aug 23 '16 at 1:31
  • 1
    $\begingroup$ @supercat I included an answer very similar to yours and gave you credit. I want the accepted answer to have all the right pieces, I hope you are not angry. I don't want to steal your rep :-o $\endgroup$ – Falco Aug 23 '16 at 11:34
  • 1
    $\begingroup$ It might help to elaborate just a little more on 1a a little bit that if W answers yes, Y must be 3 or 4 (so 2 must be X or Z); likewise if W answers no, Y must be 2 or 3 (so 4 must be X or Z). Also, while I don't think it helps with this puzzle it might be possible to eke out more than 1 bit of information from your "last" question: you can partition permutations into half-plus-one if there's one permutation that would cause you to get shot, you wouldn't be able to ask any more questions but you'd know what the correct permutation was. $\endgroup$ – supercat Aug 24 '16 at 14:43
19
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Your procedure requires that you different things in the "Y lies" and "Y tells the truth" cases, before you know which of them is Y. $\endgroup$ – Gareth McCaughan Aug 22 '16 at 10:23
  • $\begingroup$ @GarethMcCaughan what do you mean? If y is yiljob, it is already differentiated. Could you please give more details? $\endgroup$ – Sora Aug 22 '16 at 10:26
  • $\begingroup$ Ah, I understand. The point is that you can distinguish these cases by whether you get two yesses or two noes. I will edit your answer to make that a bit more explicit. (And I think your answer is correct and earlier than the other two similar ones with the same number of questions from smriti and me.) $\endgroup$ – Gareth McCaughan Aug 22 '16 at 10:31
  • 2
    $\begingroup$ Thanks for helping my answer be clearer. $\endgroup$ – Sora Aug 22 '16 at 10:34
  • 4
    $\begingroup$ @NathanMerrill asking Q1 to all 4 trolls counts as 4 questions $\endgroup$ – Ivo Beckers Aug 22 '16 at 13:21
10
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ The hypothetical is very cleverly constructed! I'm always happy with an algorithm that always has the same runtime as well, although that doesn't explore a best-case scenario outlined by user1540815. Between the two of you, both bounds were lowered! Too bad an incorrect answer was accepted, I'm impressed by your answers. $\endgroup$ – Jakob Pamp Bengtsson Aug 23 '16 at 9:50
  • $\begingroup$ @JakobPampBengtsson: The best-case scenario would be two questions. Ask troll #1 "Is the order WXYZ". Ask troll #2 if the order is anything other than "WXYZ". If both respond "Yes", the order is WXYZ. $\endgroup$ – supercat Aug 23 '16 at 14:32
  • $\begingroup$ @supercat with these two questions the order could still be YWXZ, but you can ask the question `If I would ask you "is the order WXYZ" what would yoy answer?" If he sais yes it is the solution $\endgroup$ – Falco Aug 24 '16 at 7:22
  • $\begingroup$ Explanation: W and X both answer truthfully, since indirect double-question. And Yijlob would kill you, since he does not know what he would answer, since he answers randomly, if you still live it was not Yijlob ^_^ $\endgroup$ – Falco Aug 24 '16 at 7:27
  • $\begingroup$ @Falco: You're right; there are other problem cases as well. How about Q1: Is the arrangement either WXYZ or something with X at the beginning", and for Q2 (asked of #2) is the arrangement something which isn't WXYZ, but doesn't have W in the second place". $\endgroup$ – supercat Aug 24 '16 at 7:29
6
$\begingroup$

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 :-).

$\endgroup$
  • $\begingroup$ Correct! And I would like to give the checkmark to the first person who can prove that it's not solvable in 4 questions. $\endgroup$ – Lynn Aug 22 '16 at 10:41
  • 2
    $\begingroup$ @Lynn: Four yes-no questions can only distinguish between $2^4 = 16$ cases, yet there are $4! = 24$ possible ways that the four trolls could be arranged. $\endgroup$ – jwodder Aug 22 '16 at 12:51
  • $\begingroup$ Exactly... that's the answer! $\endgroup$ – Lynn Aug 22 '16 at 13:05
  • 3
    $\begingroup$ @jwodder: The questions are yes/no questions. But the answers are yes/no/silence. For example if the first three trolls gave you an answer, no need to ask the fourth. $\endgroup$ – gnasher729 Aug 23 '16 at 0:10
  • 1
    $\begingroup$ gnasher729, that's a good point. $\endgroup$ – Gareth McCaughan Aug 23 '16 at 0:53
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ You don't yet know that X is a liar after asking the first question. X and Y may both have answered "no" and you don't know which is which. $\endgroup$ – Gareth McCaughan Aug 22 '16 at 10:24
  • $\begingroup$ Your first four questions either identify {WY}{X}{Z} (as you continue with) or {W}{XY}{Z} (which you do not). $\endgroup$ – Jonathan Allan Aug 22 '16 at 10:24
  • $\begingroup$ @GarethMcCaughan, Yup, I did not realize that. I will edit my answer. $\endgroup$ – smriti Aug 22 '16 at 10:38
  • $\begingroup$ @JonathanAllan so, is my approach is on right track? $\endgroup$ – smriti Aug 22 '16 at 10:38
  • $\begingroup$ Also, remember these are trolls - they might not know what the solution to your question is and kill you :) $\endgroup$ – Asunez Aug 22 '16 at 14:03
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Welcome to Puzzling.SE! I think you misinterpreted the question counting rules - asking the same question a second time (of any brother) counts as a second question. (it is a little hidden away in comments, I'll update the OP) $\endgroup$ – Jonathan Allan Aug 22 '16 at 13:19
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ In A2, it is possible that you asked Wudhor and Xhangar and Yiljob is left without an answer. $\endgroup$ – Sora Aug 22 '16 at 11:35
  • 1
    $\begingroup$ I meant Yiljob is the 'fourth' one, to be more clear. $\endgroup$ – Sora Aug 22 '16 at 11:36
  • $\begingroup$ @Sora - uh, yep... rethink. $\endgroup$ – Jonathan Allan Aug 22 '16 at 11:41
  • $\begingroup$ Downvoter: Why would you downvote an answer which states at the top that it is incorrect?! $\endgroup$ – Jonathan Allan Aug 22 '16 at 13:29
  • 1
    $\begingroup$ @JonathanAllan: I didn't downvote, but I initially interpreted the "Incorrect" at the top as being addressed to the other answer(er)s, saying that they were incorrect. $\endgroup$ – jwodder Aug 22 '16 at 13:45
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You can't assume that you will get lucky and be able to do it in three questions. The accepted answer has a strategy guaranteeing that it is doable in four questions, beating your answer of five. $\endgroup$ – f'' Aug 24 '16 at 12:40
  • $\begingroup$ Of course I can assume that I will get lucky. In fact that is (in my interpretation) what I HAVE TO ASSUME if I'm talking about "best-case" and "worst-case" scenarios. The OP asked how much questions youd need in minimum and in worst case. I gave two examples where three questions are enough, ergo the minimal number is smaller or equal to 3. I agree that my solution for five in the worst case might not be optimal though. $\endgroup$ – Barkas Aug 24 '16 at 12:49
  • $\begingroup$ If you interpret the question that way, it is possible in some cases to get it in two questions. $\endgroup$ – f'' Aug 24 '16 at 14:21
  • 1
    $\begingroup$ (Ask the first troll, "Are you Wudhor?" and receive the answer "no". Then ask the second troll, "Is it the case that the third troll is Xhaqan and the fourth troll is Zrowag?" and receive the answer "no". This is only possible if they are in the order YWZX.) $\endgroup$ – f'' Aug 24 '16 at 14:24
  • 1
    $\begingroup$ Because I don't believe that that is what the question is asking for. $\endgroup$ – f'' Aug 24 '16 at 16:24
-1
$\begingroup$

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.

$\endgroup$

protected by Aza Aug 22 '16 at 22:02

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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