4
$\begingroup$

You are left on a deserted island with 15 trolls and you must identify who is who to leave.

  • A tells the truth (truthful)
  • B lies (liar)
  • C always says yes (yes taker)
  • D always says no (no taker)
  • E says yes or no randomly (random)
  • F either consistently tells the truth or lies (meteorologist)
  • G tries to make up an answer and randomly decides to truth or lie (undecided)
  • H and I copy one of the other trolls randomly consistently (one-time telepathic)
  • J copies A or B randomly (joker)
  • K copies a random troll every time (telepathic)
  • L alternates copying every one of the other trolls (A>B>...>K>M>N>O>A) (teletoggler)
  • M copies H if the answer is yes and I if it's no (truthful double telepathic)
  • N is the reverse of M (lying double telepathic),
  • And O alternates truths and lies (toggler).

In these trolls, 10 of them speak English, but the other 5 speak Trollish, an unknown language.
It is discovered in the Trollish dictionary that absolutely no words sound like English 'yes' or 'no'.

However, you know the truth-teller, liar and meteorologist speak English.

What is the minimum number of questions to find out who is who?


EDIT: If a troll can't answer (e.g. G, will you lie on your next question?), he will leave and you can't ask him anymore.
Also, Trollish has ONLY ONE word for 'yes'. Same goes for 'no'.

EDIT: HARDER VERSION: If the normal version is solvable, can you solve the harder version by adding these three trolls?

P asks everyone else the question, then takes the logical xor of all the answers
(A or B or ... or O or Q or R but not all of them) (EDIT: NOT INCLUDING C OR D)
Q is the same as P but with logical and
And R is the same as P but with logical or.

This time, 13 trolls speak English and 5 speak Trollish.


EVEN HARDER VERSION: You are not allowed to ask any trolls ANYTHING about the Trollish language, like "Did that Trollish-speaking troll just say no?" and "Does (Trollish word) mean yes?".

$\endgroup$
11
  • 1
    $\begingroup$ Welcome to Puzzling, take our tour! Could you please provide proper attribution for this question? $\endgroup$
    – Auribouros
    May 13 at 9:28
  • 1
    $\begingroup$ Hi @HelloWorld! I think "meteorologist" is mispelled and is missing an O here: meteorologist. $\endgroup$ May 13 at 13:00
  • $\begingroup$ My brain hurts. Too many variables! hahaha Does each troll know the action description of all of the other trolls? $\endgroup$
    – JLee
    May 13 at 14:44
  • $\begingroup$ Seems related to puzzling.stackexchange.com/questions/49936/name-the-trolls - some of the trolls are better-explained there. $\endgroup$
    – Rob Watts
    May 14 at 3:15
  • $\begingroup$ What happens in this puzzle is a troll is asked a question it cannot give an answer to, such as if the Undecided troll is asked about if their next answer will be truthful? $\endgroup$
    – Rob Watts
    May 14 at 3:32

2 Answers 2

3
$\begingroup$

I'm going to try to answer assuming that only yes/no questions are allowed and that no funny business (e.g. coercive logic) is allowed.

[Edit: OP has confirmed that funny business is allowed (in the form of asking possibly unanswerable questions). This breaks the below argument.]

I'm also assuming that Trollish is so incomprehensible that the questioner can't tell whether two Trollish responses are the same or different - so e.g. the questioner can't ask a Trollish speaker two questions, hear two answers which sound different, and deduce that the troll has answered yes once and no once.

Let's divide the trolls into three teams, Red and Blue and Green. Team Blue will try to confuse the questioner by pretending that they are Team Red and that Team Red is Team Blue.

Team Red: A,B,F,C,D.
Team Blue: E,G,K,H,I.
Team Green: the others.

Suppose that the 10 trolls on Red and Blue speak English, and the trolls on Green speak Trollish.
Suppose that H always copies C (so both answer yes to everything), and I always copies D (so both answer no to everything).

The Green trolls are no use - any answer they give is indecipherable. The trolls E, G, and K are all able to answer any question with yes or no. The question states that these trolls make choices at random, but let's assume that in fact they always decide in such a way as to make things maximally confusing for the player by answering in a way that is consistent with A, B, F, C and D really being E, G, K, H, and I (and vice versa) in that order.

In this situation, no matter how many questions you ask, you can't be sure of the identities of all the trolls - because you can't be sure which way round Team Red and Team Blue are.

$\endgroup$
4
  • $\begingroup$ I don't think Trollish being incomprehensible is a fair assumption. What we do know is that if we hear "yes" or "no", it is definitely not Trollish. $\endgroup$
    – Rob Watts
    May 14 at 3:26
  • 2
    $\begingroup$ @RobWatts If i'm not wrong, Trollish being incomprehensible is irrelevant because the troll doesn't speak english and thus cannot understand the question asked to it in the first place so @ fblundun 's assumption which is basically "Answers in trollish don't give any information except the troll only speaks trollish" is alright $\endgroup$
    – Ankit
    May 14 at 3:55
  • $\begingroup$ @Ankit Speaking a language and understanding a language are quite different things. $\endgroup$ May 15 at 13:16
  • $\begingroup$ @fblundun Let's suppose that we already know who is the truthteller and one of the non-random green trolls (like O) answered "utt-aüt". Then, you might answer the truthteller "Is utt-aüt the Trollish answer for the word yes?". Then, it is possible to translate Trollish to English and some of the green trolls answers might be useful afterall. $\endgroup$ May 15 at 13:20
3
$\begingroup$

Partial answer

  • G tries to make up an answer and randomly decides to truth or lie (undecided)
  • J copies A or B randomly (joker)

This means that G and J answers are undistinguishible from a random bitstream independent of anything else. However, it is possible to trick them out by say, asking J something and then asking A if J's answer was truthful. But on the other hand, I don't see any advantage of using this trick.

Another trick might be to make they leave by giving them unsolvable questions. This could be useful if other trolls like K, L and P don't rely questions to trolls who left.

  • E says yes or no randomly (random)

Another random bitstream, but this one would never leave. However, giving him an unsolvable question and getting a junk answer instead of seeing him leaving might give the information that he is not A, B, F, J, O, Q, R or possibly someone else.

  • P asks everyone else the question, then takes the logical xor of all the answers

Since A is opposite to B, C is opposite to D, and M is the opposite of N, those all get zero'ed when xor'ed, leaving P's inputs being mostly junk random data, or at least very doubtful data.

Also, since his answers already includes xor of three perfectly random bits from E, G and J, it is also undistinguishable from a random bitstream. Could still be tricked out if you can get E, G and J would-be answers being xor'ed out. But I still don't see how his answers could be useful.

Perhaps, making P leave might be interesting.

  • Q is the same as P but with logical and
  • And R is the same as P but with logical or.

So, Q always answers "no" and R always answers "yes" (either in English or in Trollish). This is because that Q could only answer "yes" if everyone else answered "yes", which is impossible. Also, R could only answer "no" if everyone else answered "no", which is also impossible. They also will never leave since C and D never leave.

In these trolls, 10 of them speak English, but the other 5 speak Trollish, an unknown language.

I suggest that we should assume that "yes" and "no" in Trollish clearly distinguishable from each other like "eeut" and "brroj" instead of "kobva" and "cobfa". So, if one troll answers "eeut" I know that he speaks Trollish and that "eeut" is either "yes" or "no" in Trollish. If I ask the truthteller if eeut is the Trollish answer for the word yes and he answers me yes, then when another troll tells me "brroj" I would know that this is "no" in Trollish.

So, let's see the trolls profile:

  • A, B, C, D, F, Q and R are deterministic and independent of anything else.

  • O is also deterministic once you know which is his state.

  • C, D, E, Q and R never leave.

  • E, G, J and probably P are completely random.

  • H, I, K, L, M, N might be anything. They could be deterministic, deterministic sometimes, completely random or biased random.

Although I have no idea how to solve this optimally, let's give an upper bound:

  1. With 18 trolls, ask each two questions: "Is 2 + 2 = 4?" - Some will answer "yes", some others will answer "no", some might answer something else in Trollish. 18 questions so far.

  2. From the 13 trolls speaking English, we should try to find at least one of the truthteller (A), the liar (B) or the metereologist (F) or the toggler (O), in order to get usable answers to useful questions. Ask them the question "Is 2 + 2 = 5?". 31 questions so far.

  3. If any troll between the 13 English-speaking produces two equal answers for those two questions, they can't possibly be A, B or F. If no troll produces two consecutive equal answers for those two first questions, this means that the trolls who speak Trollish are precisely C, D, O, Q and R who necessarily must produce two consecutive equal answers. Also, B, C, D, O, Q and R never answer both those two questions correctly. A, (F is truthful) always answers correctly.

  4. From the trolls that speak Trollish or that didn't answered correctly the first two questions, ask them "Does the set of sets which does not contains themselves, contains itself?" - This tells apart B, F (if liar), G, O and P who will leave, while C, D and E will stay. 47 questions is the upper bound so far.

  5. Run out of ideas...

$\endgroup$

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.