11
$\begingroup$

TL;DR

There are 11 trolls named and you should discover their names by asking yes-or-no questions to them, directing each question to one troll. You must use the minimum possible number of questions.

If the troll is able to answer, he will say "yes" or "no" in one of their made-up languages.

If the troll is unable to answer, he will go away and you won't be able to ask him anything anymore.

There are three made up troll languages, each one spoken by three trolls.

The 1st troll tells his name promptly right at the start, but you aren't allowed to ask him anything.
The 2nd always says the truth.
The 3rd always lies.
The 4th answer either "yes" or "no" randomly.
The 5th telepathically redirects the question to one of their still present peers (except 1st) to answer.
The 6th telepathically redirect the question to either the 2nd or the 3rd trolls.
The 7th will try to produce an answer and then randomly decide if he will tell the truth or lie.
The 8th always answer "yes".
The 9th always answer "no".
The 10th will consistently either always tell the truth or always lie.
The 11th will never answer anything.


Detailed description

You are an adventurer in a journey on a distant land that a friend told you that was full of treasures. However, your adventure didn't gave any fruits. Seems that your friend was in fact just a troll instead and now you traveling back to home with empty hands. Darn! That was bad enough, what else could go wrong?

When you were crossing a bridge, a group of trolls ambushed and captured you. After a very long and dramatic fight that lasted less than 3 seconds, you are tied and chained to a rock and there is no way to escape.

Hahaha, young adventurer, you are so screwed... What do you prefer, trick or treat? You should choose if you want to be the poor-man or the food-man. Either pay us a toll equivalent to your own weight in gold or be our lunch!

You replied:

But... But... I don't have any money!

The trolls became excited:

Hmmm, then you would be a delicious piece of meat! I guess that you could be a nice sausage on a pizza...

You insisted:

No, please! I am too young to die! I am just an adventurer from the puzzling community engaged in riddles, logic puzzles, brainteasers and ...

One of them, a troll with a loud voice, interrupted you:

Wait! Did you said logic puzzles!? We love logic puzzles! Logic puzzles are excellent tools to troll out people and screw up with them! Ok, we will give you a chance to escape alive, should you prove yourself that you are a smart nerd worth to be kept living by beating our challenge. However, if you fail, thou shalt be our dinner!

We are trolls, so our challenge will be a very trollish one. Be sure that we don't simply kill the unfortunate adventurers that cross our way for no reason because this isn't much fun. We enjoy to fool and trick people around and pissing them off while laughing out of their stupidity, cluelessness and frustration before taking a bite of them.

Here is your challenge: If you want to live, you should guess correctly the name of each one of us. All of us. You are allowed to only make some yes-or-no questions and direct each of those questions to exactly one troll.

When you ask one of us something, if the answerer is able to produce an answer, he will immediatelly tell you either "yes" or "no" without further ado. If he is unable to answer however, he will retire himself from our group, going to a place not near from here, and you won't be able to direct him questions anymore. However, you still need to give the name of all of us, including those who eventually go away.

If you ask something that isn't a yes-or-no question, like "what is the name of your mother?", "what is my favorite color?" or "how many cellphones China produced last year?", we will respond by bringing you to our kitchen and start cooking. Ditto for directing any question to more than one troll.

Any idiot with a half brain would eventually pass our challenge if we give an unlimited number of questions. Since you must show that you are not just an idiot with a half brain, you are required to ask us no more than the optimal number of questions for the worst case (and it is part of your business to discover what is this number). If you ask too many questions, you'll promptly be invited to join us... through our mouths!

Also, we are quite impacient. We won't wait you think about a solution forever. We'll give you only some minutes. If you take too much time, then it will be just the time for a lunch and we're hungry.

Also, I should warn you that we trolls are very smart, intelligent and wise. We know a lot of things, much more than what you could even dream about. You can ask us "if P is equal to NP", "if the Riemann hypothesis is true", "if axions are the main constituent of dark matter", "if the coffee that your aunt prepared fourteen years ago to your mother had too many sugar or not" or even "if Lilah secretly liked you the same as you liked her when you both were in the 6th grade" - we know everything! However, we can't predict the future until it becomes certain and undoubtful.

Well, now that you already know the rules, let me introduce ourselves:

  1. My name is $\huge{😹}$ and I am the king of the trolls. If you are stupid enough to ask me anything, I will answer you enthusiastically by kindly bringing you to have a meal with us. Our chef will prepare and serve "dumb adventurer-puzzler barbecue" specially for this ocasion.

  2. $\huge{😇}$ is our knight troll. Whatever he tells you, it is the most pure expression of the truth.

  3. $\huge{😁}$, on the other hand, is our knave. Whatever he tells you, it is a pure expression of the falsity.

  4. $\huge{😅}$ is the random troll. Whatever you ask him, he will always promptly answer either "yes" or "no" based purely on some random data stream. In special, nobody know in advance what the output of that stream would be until it is readed out.

  5. $\huge{😆}$ is the telepathic troll. Whatever you ask him, he will establish a telepathic connection to one of his nearby fellow trolls except me and use it to re-ask the exact same question in the exact way that he received it. Then, he will tell you the answer that he telepathically receives after a possibly translation to his own language (if needed). If the answer is something that is not yes or no, that is exactly what you will receive from him.

  6. $\huge{😰}$ is the joker troll. When you ask him something, he will first telepathically ask the random troll about that and based on his answer, telepathically ask it to either the knight or the knave trolls.

  7. $\huge{😂}$ is the undecided troll. When you ask him something, he tries to think about your question in order to give you an answer. Before he tells you the answer, he will telepathically ask the random troll if you should learn the truth or hear a lie.

  8. $\huge{😉}$ is a very positive troll. His motto is "No matter what is the question, yes is the only answer ever".

  9. $\huge{😠}$ has a very bad humor for a troll. He is boring and unfriendly. He always answers "no" to everything and everybody.

  10. $\huge{😎}$ is a meteorologist and he pays attention to the weather... of his own imaginary planet. If it rained last week on his planet, he will tell the truth. If not, he lies.

  11. $\huge{🤐}$ has a bad medical condition. A moderator caught him another day and now he can't talk anymore! Poor troll, this is very sad. It is hard to be a troll when you can't say anything!

Oh, I was almost forgeting to mention. We trolls like a lot speaking in our own secret made up languages because this a very efficient method of trolling and annoying people. I myself will speak English, but the other trolls will produce yes-or-no answers in Trollese, Madeupish or Nonsensean, with three trolls for each language. Those languages have the feature that their dictionaries show that no two different words sound similar. But be aware that sometimes, unrelated languages may possibly share some words that may or may not share the same meaning.

Finally, you might know that there are at least some millions possible ways to assign names to trolls. In order to ensure that you are not just a very lucky guy playing with probabilities instead of a very nerdy guy playing with deterministic algorithms, we will know what is the process that you used to draw your conclusion (remember, we know everything). So, if there could be some way in which your strategy would have failed, we will make time run backwards, change the outcome of some variables that are under our control (i.e. our languages, the random data stream and the weather on the imaginary planet), restart forward-going time and ensure that you will fail (that is our trolling level - It's Over Than 9000). So, if your strategy is not the optimal one, you will be a tasty yummy guy!

Now, it is your turn. Tell one of us what is your first question.


Notes

I don't know for sure myself what the solution is. But I know for sure that this is unsolvable with anything less than...

19 questions.

I think that the solution feature something around...

28 questions.

I elaborated this question by taking inspiration from this other answer of mine. Warning: this link features insight that would be considered a partial spoiler for this question!

This question also has some relation to a problem that was dubbed as "The hardest logic puzzle ever", although I personally think that it don't deserve this name.

$\endgroup$
  • 2
    $\begingroup$ You may want to consider reducing the length of this... $\endgroup$ – Beastly Gerbil Mar 12 '17 at 13:01
  • $\begingroup$ You could try asking your brilliant troll of a friend who was caught in the same ambush. $\endgroup$ – Lawrence Mar 13 '17 at 8:22
  • $\begingroup$ Presumably telepathic troll can still ask the retired trolls questions even though you can't? $\endgroup$ – Brent Hackers Mar 13 '17 at 12:54
  • $\begingroup$ Ask every troll except for the king "Am I going to ask you another question after this?" and because trolls "can't predict the future until it becomes certain and undoubtful" and 'If a troll is unable to answer, he will retire himself from the group', they will all retire except for the king. Tell the remaining troll (the king) that he is 😹 and that TECHNICALLY he didn't SPECIFICALLY say that you needed to name retired trolls, so you're all done. And when that doesn't work, at least you only have one troll to try and out run! $\endgroup$ – Brent Hackers Mar 13 '17 at 13:08
  • 1
    $\begingroup$ So when you say we need to find out their names, what you mean is we need to find out which troll corresponds to which number, right? As in, which troll has which "superpower"? $\endgroup$ – Jack M Mar 14 '17 at 9:28
7
$\begingroup$

Found a solution! I'm not at all sure that it's optimal, meaning the trolls will eat me anyway, those assholes. In particular I don't make any use of the fact that there are three languages spoken by three trolls each [but stay tuned on that one, I've found a promising line of inquiry].

The number of questions is very variable depending on which answers the trolls give; I've counted 42 40 and it's likely to be a maximum (i.e. the actual number because the trolls would presumably time-travel to ensure it) but I didn't count the number of questions under all scenarios so it might not be.

(oh wait 42... Yeah it's the correct answer why did I even spend five hours on this)

[Later ETA: I found a way to shave one question off that total, but do I want the answer to be 41 or 42? I mean, how much do I NOT want to be eaten, really?]

[Still later ETA: I shaved off another question, I give up good-bye my dear 42]

Here it goes:

BASIC TROLL TAXONOMY
We see the trolls as falling into two groups (ignoring the King Troll whom I will ignore entirely from now on): Trolls 2, 3, 6, 7 and 10 give answers that have a relationship to the question asked, i.e. they lie or tell the truth, while Trolls 4, 5, 8, 9 and 11 are all capable of ignoring the question for their answer. Both groups can further be divided: the "truthy" trolls will either behave as Knights, or as Knaves (10 is basically one of the two we just don't know which, while 6 could behave as neither but that would reveal them too easily so they will behave as one too. 7 I'm ignoring for a reason that will later become clear), while the "self-absorbed" trolls are capable of varying their answers (4, 5) or not (8, 9, 11).

A FEW WORDS ON RANDOM AND TELEPATHIC
In those four groups, the Truthy and Invariant trolls will reliably answer like they belong in their group, but the Variable trolls could answer anything so they are basically spoilers.
Moreover, a clarification from Victor Stafusa establishes that the Random Troll's random stream is "under the trolls' control" in the sense that it's one of the things they can go back in time to change to make whichever strategy I choose fail if possible, meaning the stream is not random at all, it's optimized to make this problem as hard to solve as possible.
The same can be said of the Telepathic Troll, because it can choose to answer whatever it wants anyway (as long as there are non-retired trolls that can answer "yes" and "no" at any point, which there are because 8 and 9 will never retire), or alternatively it can copy the Random Troll and its optimized-to-mess-me-up stream.
Either way 4 and 5 can be considered interchangeable.

ON SLICING CAKES
To divide a group into four I theoretically need only two questions (asked of each troll of course); however here I will not understand the answers they give, and because they do not all speak the same language I cannot use one's answer to deduce another's. But each troll does stick to its own language, so I can compare their successive answers to each other, which is what I'll do. This means however I need three questions, because two questions only yields one comparison. These three questions will be:
To divide the Truthy group from the Invariant group: Will your next answer be a lie? will be answered by "No" by all truthy trolls (2 tells the truth that it's "no", 3 lies that it's "yes" and so answers "no", 10 behaves as one of those and 6 has no choice but to give the only answer available to them), and as a bonus will make 7 go away because Undecided Troll cannot know whether it will lie or not next question, meaning it cannot form an answer to lie or tell the truth about. Will your next answer be the truth?" similarly will be answered "Yes" by all truthy trolls; the Invariant trolls for their part will give the same answer to both questions. This means comparing the answers to both questions will separate out the Truthy from the Invariant;
And to tell the Knight-behaving truthy trolls from the Knave-behaving ones: Is 2+2=4? will do nicely. Trolls who give the same answer as to the first question are Knave-behaving (and, once we identify them as the Knave Troll or Meteorological Troll, we will know that that answer means "no") and Trolls who give the same answer as to the second question are Knight-behaving.

THE QUESTIONS COMMENCE
I actually start with the last question I mentioned, because that is a question that every troll can answer except the Silent Troll, meaning it allows me to identify him. [LATER ETA: I've just realized this isn't necessary: I can ask the questions in the order I first presented them, remember which two trolls retired from the first question and ask the Knight Troll later which is which, with 1 question. This allows me not to ask the last question to anyone who gave the same answer to the first two, saving me 2 questions (it won't be more for asshole-time-traveling-troll reasons), for a net gain of 1 question and a total number of 41, which is just plain silly honestly we all know the answer is 42)]. I will write all the answers the trolls give as a letter of the alphabet to represent that we don't understand their answer (and a different letter each since I don't know which speak which languages). So I ask each troll: "I): Is 2+2=4?" and I get the answers:
2 - A (Yes)
3 - D (No)
4 - E/F (Yes or No)
5 - G/H (Yes or No)
6 - I/J (Yes or No)
7 - K/L (Yes or No)
8 - M (Yes)
9 - P (No)
10 - Q/R (Yes or No)
11 - Goes away.
We've now identified Silent Troll and asked 10 questions (note that the Telepathic Troll wouldn't go away at this point because the Silent Troll can't talk but that doesn't mean they can't communicate telepathically).
The next question is : "II): Will your next answer be a lie?". The trolls reply:
2 - B (No)
3 - D (No)
4 - E/F (Yes or No)
5 - G/H (Yes or No) or goes away but really doesn't
6 - J (No)
7 - Goes away
8 - M (Yes)
9 - P (No)
10 - R (No).
So at this point either one or two trolls go away; if one does then I know that was the Undecided Troll. If two do then I know that the first one was the Telepathic Troll (channelling the Undecided one, which it can only do if Undecided Troll hasn't retired) and the second was the Undecided Troll. But this makes my life easier meaning the Telepathic Troll will do no such thing, so I've identified only Undecided Troll and asked 19 questions.
Finally I ask: "III): Will your next answer be the truth?" to the remaining eight trolls, for 27 questions. Their answers:
2 - A (Yes)
3 - C (Yes)
4 - E/F (Yes or No)
5 - G/H (Yes or No)
6 - I (Yes)
8 - M (Yes)
9 - P (No)
10 - Q (Yes).

Now I can divide the trolls into four (actually three) groups: the "Invariant group" are those that gave the same answer to all questions and contains 8 and 9 (and maybe 4 and 5, which could be in any group); those that gave the same answer to questions I and II but a different answer to III are "the Liar group", containing 3, 10 if the Meteorological Troll is a liar this week, 6 if it was channelling 3 for question I, and maybe 4 or 5; those that gave the same answer to I and III and a different one to II are "the Truthful group", containing 2, 10 if Meteorological Troll is Knightish, 6 if it was channelling 2 on question I and maybe 4 and/or 5. The last group, call it the "WTF are we even doing group", is those that gave the same answer to the "are you truthy" questions (so they're self-absorbed) but a different answer to the "which truthy are you" question (so they're not invariant); has no guaranteed members but could include 4 and/or 5. Call the groups I, L, T and W.

At this point there are a few things we can say. If L and T contain one or five members then we can use the guaranteed Knight or Knave Troll, and the fact we can guess "Yes" and "No" in their language from their previous answers, to identify everyone else [note this would take 11 questions at worst; this is relevant later]. If WTF group contains two members we can separate out the Knight, Knave, Joker and Meteorological Trolls using the question "Are you a Knight" (for members of the Truthful group) or "Are you a Knave" (in the L group), to which the Knight, Knave and Joker Trolls will give the same answer and the Meteorological Troll a different one. So, from the principle of maximum hardness on the part of the trolls we can assume the L and T groups contain three members each or two and four members. This implies that WTF group is empty and the Invariant group contains only 8 and 9.

SO WHAT DO WE DO NOW
So far, 2 (and all other members of T by definition) will have answered in the pattern "same-diff-same", and 3 (and all other members of L) will have answered in the pattern "same-same-diff". Call those patterns "SDS" and "SSD". Now if I ask all members of group T, "Are you the Knight Troll?" I am guaranteed that 2 (and 6 if it's there) will answer "yes", while 10 will answer "no", meaning if 10 is in group T I am guaranteed to end up with two patterns: SDSS and SDSD. I can do the same thing in group L with the question "Are you the Knave Troll?", yielding the patterns SSDS and (possibly, guaranteed only if 10 is in L) SSDD. Let's call the patterns that the Knight or Knave produces K-type patterns, and patterns the Meterologist produces M-type patterns. (I have now asked 33 questions).


IT GETS INTERESTING
At this point a few configurations can give it all away for me. If any group contains only one K-type pattern, then I've identified a Knight or a Knave and I know I'll get all the names eventually (forget optimal number of questions for now...). If there is only one M-type pattern, I've identified my Meteorological Troll and I know the weather on his planet last week so we're good. This leaves only a few configurations where I would lack information, i.e. a few configurations that are possible given trolls go back in time etc. If groups T and L have 3 members each, both groups will have two K-type trolls and one M-type troll. If the groups have 4 and 2 members, the 2-member group will have two K-type trolls, and the 4-member group will have two K-type trolls and two M-type trolls. Or put another way, we have 4 K-type trolls and 2 M-type trolls, with 2 K-type trolls in each group and the M-types trolls either both in one group or one in each group.

Now, if we have a 3/3 distribution, if I ask a troll in L or T group "Is the Meteorological Troll in your group?" (or, if the trolls don't like groups, ask "Is the Meteorological Troll one of this troll, that troll or that other troll?", it works out), the Knight, Knave, Joker and Meteorologist will all say the same thing, namely "yes" if 10 is in T and "no" if 10 is in L. The Joker is K-type so three out of four K-types will necessarily give the same answer, meaning that there will be one group where both K-types maintain the same pattern. That pattern will tell us whether the answer was "Yes" or "No" (for example, if it's in T-group and the pattern is SDSSS the answer is "Yes", because "S" is "Yes" for the Knight Troll), meaning we have unambiguously identified our Meteorological Troll, and we know whether it's lying or telling the truth this week, meaning we can identify all the other trolls.
Now notice that to come to this conclusion we only needed to interrogate the K-type trolls. This means that in the 4/2 configuration we can get the same result just by moving one M-type troll into the other group: if it happened to be the Meteorological Troll it would no longer give the same answer as 2, 3, and 6 because we'd have a truthful 10 in with the liars or vice-versa, and we need to take that into account once we know which group 10 is in, but since we only need to ask the K-type trolls it's irrelevant to finding where 10 is in the first place. In fact... we don't even need to ask all the K-type trolls! If we ask a group and both K-types give the same pattern then we're good. If we unluckily start asking the group in which one of the K-types is 4 or 5, this troll will break the pattern, meaning we won't know which pattern the actual 2 or 3 gave and will need to ask the other group. But since we know that in that group both K-types will follow the same pattern we only need to ask one. So, we have identified Meteorological Troll with 3 questions putting us at 36.

WRAPPING IT UP Now all we need to do is ask the Meteorogical Troll questions like "Is this the Knight Troll?" and go from its answers, which we know are true or false depending on the group it's in and we know what's yes and what's no depending on its pattern of answers so far. We need 2 questions to identify the Knight or Knave in the two groups of two K-types; 1 question to identify the remaining M-type which is either Random Troll or Telepathic Troll; 1 question to distinguish Joker Troll from whichever of the two was the other K-type; and 1 question to identify the Positive and the Bad Humor Trolls (which have been waiting patiently in their group all this time, Invariant to the end; I hope Positive Troll found ways to help Bad Humor Troll to pass the time).


And so we get to 42, which is so obviously the correct answer I say we can stop here. It breaks my heart but now that I've shaved two questions from the total I need to face reality that Victor Stafusa did not, in fact, come up with the Ultimate Question to Life, the Universe and Everything :( Total questions so far is 40 (supposing we did kick out two trolls on the first question as described in the [later ETA] brackets). Theoretically we should count all the answers at the previous points of "now we have identified this troll we can trivially get the others" to make sure one of those paths doesn't force us to ask more questions than that, meaning the trolls might push us there. I've done that with the "there is only one troll in L or T" scenario, and that gets us to a mere 27+11=38 questions. I'll assume all other paths similarly need fewer questions.



NOTES AND APPENDICES


HEY, COULDN'T YOU KICK MORE PEOPLE OUT?
I don't see the point. 4, 8 and 9 will never leave, and 5 can never be forced to leave. 5 and 4 are the big spoilers, and the heart of my strategy is to identify a reliable truth-teller or liar so it can tell me what the others are; this is useless if I make the truthy trolls leave. I tried to see if weeding out the larger of the L and T groups could help, but there are two random spoiler trolls, insofar as there is one in each group (and therefore there will be one in each group) this strategy doesn't leave me further informed.
It should also be noted that it might look like asking questions that might make a troll go away provides more information than those that don't, because we have three potential answers ("yes", "no", leave) instead of two. However this is ignoring the kind of trolls we're talking about here. The answers "yes" and "no" as such provide next to no information from 4 or 5, and neither of those can be made to leave anyway. 6 cannot be made to leave in a way that won't also make 2 and 3 leave. "Leave/don't leave" can only be used to distinguish (2, 3, 6, 10) from (4, 5), and not even 5 actually because 5 can leave if it makes our lives harder. It is hard to see how adding "leave" to the mix allows one to discriminate such small groups better than a few "Is this one the Knight/Knave/Joker/etc Troll?".

WHAT ABOUT THE LANGUAGES? SOME SHARE A LANGUAGE REMEMBER?
I remember, and in the real situation this would very probably allow to solve the problem quicker, I just don't see how to do it in a deterministic way in advance. We don't know which three trolls share a language. We cannot deduce from two trolls saying the same thing that they speak the same language; "No" in Madeupish might be "Yes" in Nonsensean. We cannot even be sure we will hear all the possible words in the first question; for example, if 2, 8 and 10 all speak Trollish and all answer "Yes" then we won't have heard Trollish "No". If we have, say a T group with 4 members then we know at least two will speak the same language, meaning there will be two identical "Word1 Word2 Word1", but is it "Yes No Yes" or the Random Troll and Telepathic Troll both saying "No Yes No"? The beauty of the pattern is that it's irrelevant whether a given troll is saying "Yes" or "No" - for example, for the question "Is the Meterological Troll in your group?", the Telepathic Troll might be K-type but giving the opposite answers from the Knight Troll. If it chooses to break the pattern, then two K-types in the other group necessarily had the same pattern and we can go by their answer. If it chooses to maintain the same pattern, thus answering the opposite of what the Knight Troll said, it doesn't matter that its answer was "No" when the Knight Troll's answer was Yes, or that we don't know which is the Knight Troll and which is the Telepathic Troll; we know the real answer is "10 is in the T group" because we know what Knight Troll's answer would be given the pattern, and they both follow the same pattern.
The closest thing to useful I can think of is once we've identified 10, 2 and 3, maybe also 6, and we know exactly what "yes" and "no" mean to each, that might be enough information to tell which of the Invariant trolls has been saying "Yes" and which has been saying "No", thus saving a question to identify them. But I'm not quite sure how to swing it, considering some languages might be the exact inverse of others.
tl;dr: It is entirely plausible, even probable that there is a way of improving this answer based on using the fact that every three troll shares a language, but finding it seems like a lot of work to me. As for whether using that information allows a superior, completely different answer, I can't speak to that.

HOLD THE MOTHERFLIPPIN 'SEND' BUTTON
I have just realized that with the two "are you truthy" questions, and if 4 and 5 try and pass for Truthy which according to the previous reasoning they should (this might change depending on where this goes), I end up with a whopping 7 "No"s on one question and 7 "Yes"es on the other! Victor is right, surely we can do something with this.

1) I am guaranteed to hear all "Yes"es and "No"s after the second question.
2) The distribution of "Yes"es is the following (Trollish=T, Whateverese=W and Nonsensean=N - technically I should call them "language 1", "language 2" or something because I don't know which language is which, but I ultimately don't care. And neither do the trolls, because they're trolls) :
T[1], W[3], N[3] or
T[2], W[2], N[3]
So we'll hear at least one group of three trolls saying the same thing. Let's assume that "No" in at least one language sounds like "Yes" in at least one other, because these languages are designed to confuse; you know if it isn't true the trolls will even go back in time to change the languages to make it true. Meaning for each configuration, one element will be added to a given language because there were 7 "Yes"es in varying languages and 1 "No" that sounds like a "Yes" in one of those languages. So the configuration will actually look like:
T[2], W[3], N[3].
In which one of the triplets is 3 "Yes"es, and one of the triplets or the double contains a "No" in a different language.
* * * and that's all I've got so far * * *

$\endgroup$
  • $\begingroup$ I frequently add <br> inside spoiler tags to force break lines to be in the correct places. $\endgroup$ – Victor Stafusa Mar 16 '17 at 20:36
  • $\begingroup$ @VictorStafusa Thank you ! The whole thing looks more readable now, and I think I've found a solution. $\endgroup$ – Oosaka Mar 16 '17 at 23:03
  • $\begingroup$ I will take some time to carefully check all of that, but seems that you are more or less correct. Maybe you might reduce the total number of questions to 38-41 if the final questions have 3 possible outcomes: yes, no or leave and all those different outcomes determine different cases (and the troll being asked to is disposable). Meanwhile, I recommend you to divide your answer in "chapters" like I did in this answer to make it easier to mentally digest all of this. $\endgroup$ – Victor Stafusa Mar 16 '17 at 23:36
  • $\begingroup$ Also, seems that you are negleting some aspects of the trolls speaking different languages (not sure though). Anyway, great answer so far! $\endgroup$ – Victor Stafusa Mar 16 '17 at 23:37
  • 2
    $\begingroup$ I assumed that the undecided troll would be able to answer any question that the knight or knave could answer depending on which one it randomly asked. After reading your solution and re-reading the undecided troll's description I can see that my understanding of that troll's logic was totally WRONG! +1 Great explanation. Sadly, I recon troll #1 is probably a bit of a knave and you'd still get eaten even if this is optimal. See you in the lower intestine! $\endgroup$ – Brent Hackers Mar 17 '17 at 13:56
2
$\begingroup$

This may or may not work and it doesn't cover every possible series of events and I'm definitely still getting eaten BUT maybe this will be helpful to someone... Also, as pointed out by @VictorStafusa it didn't take into account the fact that the trolls don't all speak the same language.

My strategy (if you can call it that): Identify the knight, recall the order that you ask the trolls the questions, and don't speak to the king!

Ask all 10 trolls "Will you answer either silently or honestly to the next question that I ask?"

Only trolls that 1) answer randomly, or 2) ask another troll, or 3) definitely answer "honestly or silently", or 4) always answer with a YES, can respond with a YES.

If a troll answers NO, Ask them "Will you answer NO to my next question?" to guarantee that the KNAVE retires. You can then be (and therefore probably are, due to the sods-law rule) left with KNIGHT, RANDOM, TELEPATHIC, JOKER, UNDECIDED, POSITIVE, and METEOROLOGIST.

Ask all 7 trolls (separately) "Am I a Troll?" Any trolls that can only answer YES retire. The KNIGHT will answer NO, The JOKER (if he hasn't already disappeared from trying to ask something of the missing KNAVE) will answer YES (because they'll have asked the KNIGHT your question and gotten a different answer) or disappear. If a troll answers YES, then disregard them. This leaves you with the KNIGHT, RANDOM, TELEPATHIC, and UNDECIDED trolls.

Identify one of the remaining trolls as TARGET-A. Ask the remaining trolls "Might TARGET-A troll answer randomly to a yes/no question?". If no trolls answer YES then the target is the KNIGHT (which he wont be because then you'd need fewer questions), otherwise you will get at least one YES and you can disregard TARGET-A.

Identify TARGET-B from the remaining trolls and ask the other two "Might TARGET-B troll answer randomly to a yes/no question?". At this point, if both answer NO then TARGET-B is the KNIGHT, and if their answers are different, then the one that answered YES is the KNIGHT, so (probably/definitely) the two will both answer YES and you can disregard TARGET-B leaving you with the KNIGHT and one RANDOM, UNDECIDED or TELEPATH.

Designate the two remaining 'Target-C' and 'Target-D'. Ask Target-C "If I ask Target-D a question, could they tell a lie?" The KNIGHT will answer YES, and the others may say either YES or NO (so we assume we'd definitely get a YES to compound the problem).

Ask Target-D "Could you tell a lie?". If the answer is yes, then TARGET-C is the KNIGHT, otherwise TARGET-D is. You can now use the knight to identify the other trolls where you couldn't be certain about their identity. If you remember the order, you should all ready have definitively identified one or two, or at least narrowed down the possibilities. This still leaves you eaten because (by my guesstimaton) I'd have used at least 32 questions... I hope you have better luck.

$\endgroup$
  • $\begingroup$ They won't answer in English. The telepathic troll ask something to one their nearby trolls, so if he retires, it is not because it asked something to a missing troll, it is because he asked something to a troll that couldn't answer. If you ask the trolls "Am I a troll?", since the honest answer is trivially determined as "no", only troll #11 will retire. $\endgroup$ – Victor Stafusa Mar 14 '17 at 15:08
  • $\begingroup$ I would start by asking each troll what their word for "Yes" is. The no-talking troll will leave. Then ask them all what their word for "No" is. Granted that's already 19 questions asked, but now you have an idea on who speaks which languages and who might be random. $\endgroup$ – mkinson Mar 14 '17 at 16:26
  • $\begingroup$ @VictorStafusa Good point about the languages. I didn't take that into account at all! I didn't say that asking "Am I a troll?" could eliminate the TELEPATH but with the KNAVE gone, the JOKER who can now only "re-ask the exact same question in the exact way that he received it" of the KNIGHT, and the KNIGHT would answer NO if asked directly by you, but the KNIGHT would answer YES to the JOKER. I may have that wrong but I've decided that this puzzle was just a bit out of my league anyway. Still, I hope that if anyone does read my answer it will be more useful than a hindrance. $\endgroup$ – Brent Hackers Mar 15 '17 at 8:42
  • $\begingroup$ @mkinson The no-talking troll won't leave; it will just answer "no". (actually I'm wrong: the trolls will eat you because "what's your word for 'yes'" isn't technically a yes-or-no question) $\endgroup$ – Oosaka Mar 16 '17 at 19:43
  • $\begingroup$ @RozennKeribin Technically they will only answer "Yes" or "No". It doesn't specifically state that you cannot ask them what their word for "Yes" or "No" will be, only that if they cannot answer one or the other they will leave. $\endgroup$ – mkinson Mar 17 '17 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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