Is This Even Possible?

[theseum]

You've all heard of the daemons who always lie and always tell the truth... Here's a new twist.

There are three daemons. One always tells the truth, one always lies, and one answers randomly. You can ask them any yes or no question. Additionally, they answer in a language that you don't understand. Given three questions, how do you figure out which is which?

I don't know the answer, or if it can be done for that matter. Also I forget the number of questions that you're supposed to have, try it in 5 if you can't get it in 3.

[Token]

Do you know what the words for yes and no are? If you do:

Spoiler:

You can do it in three. Label the demons A, B and C, and choose a particular yes/no word, say X. Ask daemon A "If I asked you whether it was the case that either [B always tells the truth and C answers randomly] or [B answers randomly and C always lies], would you say X?" If they say X, address your next question to C. Otherwise, address it to B. Ask the one you choose "If I asked you whether you always tell the truth, would you say X?" If they say X, they always tell the truth. If they don't, they always lie. Then ask the same one "If I asked you whether A answers randomly, would you say X?". If they say X, A answers randomly. If the don't, A takes the opposite truthfulness to the one you're addressing. You can then fill in the third demon by elimination.

If you don't:

Spoiler:

You can do it in four, by asking a random question initially, calling the answer X, and otherwise following the three question case above. I don't believe there's any way to do it in three, as you need lg 6 > 2 bits of information, and you can't be guaranteed any information out of the first question beyond what one of the possible answers is. I' not sure if it's possible to formalize or invalidate that argument, though.

[Nitrodon]

About the second case:

Spoiler:

The first answer gives no information beyond identifying one word for yes or no. The yes/no words can be described as "the answer given to the first question" and "the answer not given to the first question", and reducing them to these labels does not remove any information. Since you know what the answer to the first question will be under these labels, you get 0 bits of information from it.

[TheGrammarBolshevik]

Isn't the second case just the same as this (Spoiler note: The solution is on that page, a little ways down)?

[jestingrabbit]

This got a bit of attention during days gone by

viewtopic.php?f=3&t=273&hilit=+gods

but the problem without knowing the words for yes and no is novel for us here.

[Fat Pigeon]

I think I might have somehow oversimplified the problem because I think this works and I'm working it out at 3 AM, so I might have mangled my answer a tad.

Spoiler:

First question: Ask each daemon if he is a liar. The liar and truthteller will say "no." The random will answer "yes" or "no." Either way, whichever answer occurs more than once means "no." If you're lucky and the random daemon says "yes", but let's assume he doesn't.

Second question: Ask each daemon if he is the random daemon. If you receive two "yeses" you can now identify the truthteller because he'll answer "no." If you receive two "noes" you can identify the liar because he'll answer "yes."

Third question: Assume the daemons are in a row (A, B, C) and you've identified daemon A as either the truthteller or liar (it doesn't matter which, really). Ask daemon A if the random answerer is daemon B. The truthteller will say "yes" if correct, otherwise it's the liar and now you've identified all three. The liar will say "no" if correct, otherwise it's the truthteller and now you've identified all three.

[jestingrabbit]

I think I might have somehow oversimplified the problem because I think this works and I'm working it out at 3 AM, so I might have mangled my answer a tad.

Spoiler:

First question: Ask each daemon if he is a liar. The liar and truthteller will say "no." The random will answer "yes" or "no." Either way, whichever answer occurs more than once means "no." If you're lucky and the random daemon says "yes", but let's assume he doesn't.

Second question: Ask each daemon if he is the random daemon. If you receive two "yeses" you can now identify the truthteller because he'll answer "no." If you receive two "noes" you can identify the liar because he'll answer "yes."

Third question: Assume the daemons are in a row (A, B, C) and you've identified daemon A as either the truthteller or liar (it doesn't matter which, really). Ask daemon A if the random answerer is daemon B. The truthteller will say "yes" if correct, otherwise it's the liar and now you've identified all three. The liar will say "no" if correct, otherwise it's the truthteller and now you've identified all three.

When you ask a question, you have to direct it to one and only one daemon.

[Zetetic1123]

Old puzzle: http://philosophy.hku.hk/think/logic/hardest.php

Here is the solution if you don't want to actually work it out since it is quite difficult:
http://www.hcs.harvard.edu/~hrp/issues/1996/Boolos.pdf

[Puck]

In the puzzle you linked, it does not say the third god "answers randomly", it says the third god "speaks truly or falsely at random". These are two different ideas, since whether or not you lie, the answer to "Are you answering this question truthfully?" will always be Yes.

I am not sure whether or not the OP intended that it is possible for the Random god to answer No to such a question. However, both variations are apparently possible in 3 questions.

[mike-l]

In the puzzle you linked, it does not say the third god "answers randomly", it says the third god "speaks truly or falsely at random". These are two different ideas, since whether or not you lie, the answer to "Are you answering this question truthfully?" will always be Yes.

I am not sure whether or not the OP intended that it is possible for the Random god to answer No to such a question. However, both variations are apparently possible in 3 questions.

In most solutions I can think of,

Spoiler:

your first question is used to make sure you aren't talking to random for the 2nd and 3rd question. It doesn't matter how random answers for this strategy

If you don't know the words for yes and no, I don't think a solution exists, but every time I try to prove it, it fails. Here are my thoughts

Spoiler:

Upon hearing the answer to the first question, the only information you have is what one of the words is. However, after asking two more questions, the first answer may provide information. Since you need to distinguish between 6 possibilities, any solution has to get information from the original question eventually. I feel like this means you have to figure out which word is yes and which is no, but the puzzle is solvable if you know the words for yes and no but not what they mean, and of course in doing that you can't figure out what they mean, so this isn't necessarily true.

Because of the above, it's impossible to guarantee the 2nd question isn't posed to random. This makes things (much?) harder if random answers completely randomly instead of randomly truthful or randomly falsely. However, if you don't pose your first 2 questions to the same person you guarantee at least one of them was not random.

In the version where you know what words are available, you get around figuring out which word means which by asking if they would answer with one of the words, or by asking if one of the words means yes/no as part of the question. This isn't possible in the first question, but maybe something along these lines is? (In fact, if a solution exists, it almost has to be along these lines)

[akashra]

Isn't the second case just the same as this (Spoiler note: The solution is on that page, a little ways down)?

Almost. THe way he's described it, his third demon answers truly randomly, whereas the god in L'indovinello più difficile del mondo answers either truthfully or untruthfully randomly. There's a big difference - making it meaningful, but not random. It should be better described that the god sometimes tells the truth for more clarity. In the demon example, there's no sometimes in it - his answer is just complete gibberish, he need not even understand the question.

[ARandomDude]

If I recall correctly, the solution to the two daemon question was along the lines of

Spoiler:

What would the other guy say is the correct door/path/etc.

If you asked the question and pointed to the daemon who answers randomly, what kind of answer would you get?

[jestingrabbit]

If I recall correctly, the solution to the two daemon question was along the lines of

Spoiler:

What would the other guy say is the correct door/path/etc.

If you asked the question and pointed to the daemon who answers randomly, what kind of answer would you get?

I think it would require a special "third answer". I think its sometimes presented as the demons head exploding.

[Isvan]

Spoiler:

I think you can't really ask that question at all, since it's not a definite yes/no answer in this case. It's like asking the demon who only answers the truth 'What colour are my eyes?'. You can't answer it with a yes/no, so the question is useless. To solve this in the original two-doors puzzle, you would have to ask 'If I asked the other guy what was behind his door, would he say yes?' which is effectively the same thing in those circumstances. I guess you can't ask it here though, because you don't know what the wod for 'yes' is so you can't ask if it would be said... : /

[jestingrabbit]

Spoiler:

I guess you can't ask it here though, because you don't know what the wod for 'yes' is so you can't ask if it would be said... : /

You can find a work around for this if you know the words for yes and no ie if you know that the words for yes and no are either da and ja or ja and da, for instance. So you have to pick apart "language that you don't understand".

[undecim]

Someone keeps adding new stuff to this. First it was one question with a saint and a liar, then someone added a second question and /b/tard, and now someone says we can't speak their language, and changed it from finding a correct path and telling which person is which.

Spoiler:

It is impossible.

Because you are trying to identify each daemon, rather than determine which is a safe door to open (or whatever the goal is of variation of these riddles you prefer), your possible outcomes have gone from 2 to 6. Since there are 3 yes/no questions that can be answered, you have 3 bits of information you can receive. However, two bits are lost in uncertainty (one with the language barrier, and another with the random-answerer), giving you 1 bit to determine one of 6 possible outcomes which is not possible.

There are, of course, variations of this that are possible. If you had 5 chances to ask a question, you would have 3 bits of useful information, which is enough.
First, we'll label the daemons A, B, and C

1. Ask daemon A "Do you ever tell the truth?". [Either this answer is yes, or daemon A is the random-answerer]
2. Ask daemon A "Would you answer 'Does daemon B ever lie?' with the same answer as my previous question" If he says the same thing as last time, ask the last three questions to daemon C. If not, ask daemon B . [This assures that you are not talking to the random answerer.]
3. The last three questions can be asked in the form of "Would your answer to 'Was the first question I asked answered truthfully?' be the same as the truthful answer to '[question]?'" For any non-recursing [question], if he answers with the same word as daemon A did to your first question, the truthful answer to [question] is "yes", otherwise, it is "no". Using such a method to ask the last three questions, determining the identity of each daemon is trivial with process of elimination.

Another variation would be that you are trying to determine which of two doors leads to (for example) a treasure room, as opposed to a room filled with poisonous gas. This you can do with three questions:
First, we'll label the daemons A, B, and C

1. Ask daemon A "Do you ever tell the truth?". [Either this answer is yes, or daemon A is the random-answerer]
2. Ask daemon A "Would you answer 'Does daemon B ever lie?' with the same answer as my previous question" If he says the same thing as last time, ask the next question to daemon C. If not, ask daemon B . [This assures that you are not talking to the random answerer.]
3. Ask B, or C "Would your answer to 'Was the first question I asked answered truthfully?' be the same as the truthful answer to "Does the door on the left lead to the treasure room?'" If he responds with the same word as A did to your first question, take the door on the left, otherwise, take the door on the right.

[lordatog]

Spoiler:

It is impossible.

Because you are trying to identify each daemon, rather than determine which is a safe door to open (or whatever the goal is of variation of these riddles you prefer), your possible outcomes have gone from 2 to 6. Since there are 3 yes/no questions that can be answered, you have 3 bits of information you can receive. However, two bits are lost in uncertainty (one with the language barrier, and another with the random-answerer), giving you 1 bit to determine one of 6 possible outcomes which is not possible.

Spoiler:

While I agree that it is probably impossible, I don't buy your reasoning. In particular, you claim that one bit of information is necessarily lost due to one of the answerers being random, and this is not true. Take the variation of this puzzle which is identical except that you know what the words that mean "yes" and "no" are (though you don't know which of them is which). You still have access to 3 bits of data, still have to distinguish between 6 possible scenarios, and there's still an answerer who acts at random - and yet this version is possible. Token has provided a full solution farther up the page. So, while the fact that one of them answers at random hinders you, it does not cost you a full bit of data. Nobody has yet proven that not knowing the words for yes and no costs you a bit either, even though it almost certainly costs you enough information to make this puzzle impossible to solve 100% of the time. So... assuming that, in the case where you fail to deduce which is which, you are allowed to guess, what strategy provides you with the best chance of correctly identifying all three of them?

[Comm]

It can't be solved.

The "random" deamon might "randomly decide" to always tell the truth, in which case he is (and always will be) identical to the deamon that *has* to tell the truth.

If you have an infinite amount of questions, you can wait for him slip up of course, but with a finite (any specific) number of questions, it's not possible (for some instances of the problem).

[Nitrodon]

It can't be solved.

The "random" deamon might "randomly decide" to always tell the truth, in which case he is (and always will be) identical to the deamon that *has* to tell the truth.

If you have an infinite amount of questions, you can wait for him slip up of course, but with a finite (any specific) number of questions, it's not possible (for some instances of the problem).

This is not correct. The "random daemon" is still the "random daemon", and any questions regarding whether that particular daemon is random will be answered accordingly. It is generally implicitly assumed in this type of problem that the daemons/gods/villagers/whatever all know each other's identities.

[Davecom3]

It is possible depending on definition of Random. Is he giving randomly true or false statements or is he giving the answer totally at random. An answer given totally at random means the demons cannot be identified clearly in 3 questions as Random may be giving answers that would fit Truth or fit Lie's answers and actually deciphering this would be nigh impossible.

Actually in this case, you'd have to ask a first question that neither Truth nor Lie could answer, then watch to see 2/3 chance of a demon not answering your question. If the demon answers this question, you have successfully identified Random.

After this question, if you get an answer, you just have to ask two questions, in the form of "Would you say my eyes are blue?" and "Are my eyes blue?" to one of the other demons. Differing responses means that demon is Lie; similar responses means that demon is Truth.

If you get no answer, you ask the same sort of question to the person who didn't answer. Unfortunately, you have yet to determine what word means yes and which word means no, which makes things more tricky. I guess I'd have to come back to it.

[NumberFourtyThree]

Spoiler:

In any case, there is never a need to discover which word means yes and which word means no, as a self-referential question can essentially define a new yes and no.

If you don't know what the words for yes and no are it will take an extra question to discover one of them. Once you know one of the words you can discover the answer to any arbitrary question given that you are not asking it to the random one.

For instance, assuming the words are "da" and "ja" as is traditionally done with this problem, if you ask "If I asked you if X were true, would you say "da"?", he will answer "da" if X is true, and "ja" if it was false.

You can use a question to discover one who you can be sure is not random. Calling them A, B, and C, ask A "If I asked you if B was random would you say "ja"?". If he answers "ja" that means either B is random or A is and happened to answer that way, so you know C is not random. If he answers "da", then either B is not random or A is random, in which case B is still not random.

Once you know that, you can simply ask to find out which is which or in alternate versions whichever facts you need to find out. Note that if you interpret random to mean "randomly choose to lie or tell the truth" rather than "randomly say either yes or no" then this question form still works, but you no longer need to be sure you aren't talking to random.

[mike-l]

<solution>

Excellent, now that there is yet another full solution given in this thread, it will only be a matter of time before someone else comes along claiming it's impossible.

[reffu]

In this scenario I would probably manage to create a paradox. I will call them 1, 2, and 3 to explain. If I asked 1 "Would 2 answer my question truthfully?, then asked him the same about 3. and finally asked 2 about 1. One of them would be answering a question about the random one. In that case there is no definite answer and yet they have to answer my question yes or no. Simple paradox.

[lordatog]

In this scenario I would probably manage to create a paradox. I will call them 1, 2, and 3 to explain. If I asked 1 "Would 2 answer my question truthfully?, then asked him the same about 3. and finally asked 2 about 1. One of them would be answering a question about the random one. In that case there is no definite answer and yet they have to answer my question yes or no. Simple paradox.

You have to ask yes or no questions. If your question cannot be answered with either yes or no, then it isn't a yes or no question and you're not even allowed to ask it.

[clickz]

@edit: my bad, didn't read the part about not knowing the language

[tastelikecoke]

Spoiler:

Ask them "Do you like cake" truth guy says no, liar guy says yes and random guy says random cause the cake is lie.

[redrogue]

Spoiler:

I remember this question from Philosophy 101. If I recall, you do something like this:

First question (figure out a word for yes or no): "Do you like pie?" Answer: "Blarg". At this point, we don't know if he likes pie or not or if he was lying, but we have a word that either means yes or no.

Next, we need to find a demon that ISN'T random. It doesn't matter if you end up with the liar or the truthteller. So my next question would be a (I'm guessing) a three part question, like so ("Does 'blarg' mean 'yes' and are you true and is he (point at another one) random?"). Depending on who you are talking to, you'll ether get 'blarg' or 'not blarg'. Might need to replace "and" with "if and only if" now that I recall. Yeah, definitely if and only if. That way, you cancel out truth or liar with XNOR logic. You'll get "blarg" if you are pointing to random, and "not blarg" if you aren't (alternatively, if you happened to ask random the question, you still end up with true or false, since the remaining two aren't random).

At this point, I can only assume that I only know one word ("blarg"), and I still don't know if it is true or false. But I've found a demon that is either true or false.

My last question would be posed to the one I've established as non-random to determine the identity of the other demons. Something like "Does 'blarg' mean 'yes' if and only if you are true if and only if he (the first demon I asked) is false"

If the answer is 'Blarg' - The first demon I spoke to is false, the one I'm talking to is true, and the third demon is random.
If the answer isn't 'Blarg' - The first demon I spoke to is random (aha!), the one I'm talking to is... shit.

Maybe we do need four questions. Or perhaps I need to work in a known true statement "...if and only if my shirt is red." I'll have to think about this some more.

[Trebla]

<solution>

Excellent, now that there is yet another full solution given in this thread, it will only be a matter of time before someone else comes along claiming it's impossible.

Except his full solution fails. His solution relies on knowing the words ahead of time, which is explicitly stated that you don't.

His solution can be shown wrong by a simple scenario in which it fails. He states: "assuming the words are "da" and "ja" as is traditionally done with this problem"

1) (to A) If I asked you if B was random would you say "ja"?

Answer: Plip

When you assume you have information you don't have, of course you can solve it. I can solve it in zero questions if I assume that A is the truthteller, B is the liar, and C is the random one. See how trivial it is when you do that?

Edit: I suppose it's not explicitly stated you don't know the words for yes or no, but the implication is clear to me. I suppose it could easily be interpreted the other way.

[mike-l]

Except his full solution fails. His solution relies on knowing the words ahead of time

Once again, this has already been discussed in the thread. If you know the words ahead of time, it's possible, and there are numerous solutions posted.

I don't think it's possible if you don't know the words ahead of time (and I think that's the consensus here), but as far as I can tell noone has put forward a correct proof that it can't be. Any such proof must rely on the fact that you don't know the words, since it's possible to do if you do.

[Trebla]

Once again, this has already been discussed in the thread. If you know the words ahead of time, it's possible, and there are numerous solutions posted.

I don't think it's possible if you don't know the words ahead of time (and I think that's the consensus here), but as far as I can tell noone has put forward a correct proof that it can't be. Any such proof must rely on the fact that you don't know the words, since it's possible to do if you do.

Well, that's what makes it hard If you do know the words ahead of time, then it's essentially the same as knowing the language.

Spoiler:

The only difference is the minor level of abstraction to force a double-negative (or positive) by changing your first question directed at God A from "Is God B Random?" to "If I asked you if God B is Random, would you say 'soandso'?"

The question sequence is the same, the phrasing is the only thing that changes, and doesn't really add any difficulty. I certainly have trouble ascribing this as the "hardest logic puzzle" ever (as is claimed on wikipedia) if it's either a) that easy or b) impossible.

[mike-l]

Well, that's what makes it hard If you do know the words ahead of time, then it's essentially the same as knowing the language.

Figuring that out is part of the trick of the puzzle. Dealing with the fact that one answers randomly is the second trick of the puzzle, and getting around the lying/truth is the third trick fo the puzzle (in roughly descending order of difficulty).

I would say it's not 'easy' since a number of people have come to this thread claiming it's impossible for one wrong reason or another.

[dawolf]

Spoiler:

In any case, there is never a need to discover which word means yes and which word means no, as a self-referential question can essentially define a new yes and no.

If you don't know what the words for yes and no are it will take an extra question to discover one of them. Once you know one of the words you can discover the answer to any arbitrary question given that you are not asking it to the random one.

For instance, assuming the words are "da" and "ja" as is traditionally done with this problem, if you ask "If I asked you if X were true, would you say "da"?", he will answer "da" if X is true, and "ja" if it was false.

You can use a question to discover one who you can be sure is not random. Calling them A, B, and C, ask A "If I asked you if B was random would you say "ja"?". If he answers "ja" that means either B is random or A is and happened to answer that way, so you know C is not random. If he answers "da", then either B is not random or A is random, in which case B is still not random.

Once you know that, you can simply ask to find out which is which or in alternate versions whichever facts you need to find out. Note that if you interpret random to mean "randomly choose to lie or tell the truth" rather than "randomly say either yes or no" then this question form still works, but you no longer need to be sure you aren't talking to random.

This doesn't work.

"If I asked you if B was random would you say "ja"?". If he answers "ja" that means either B is random or A is" - ja could mean no in his language. You don't know if it's yes or no he has replied.

Spoiler:

I would ask every god in turn whether the sky was blue, whether a red rock is red....two of the gods will answer whatever they answer for yes and no, the 3rd god will change his answers. So that gets you the random god, say that's god C. Then you ask god A what B would reply to a question, say "is the sea wet?" and the answer you get back should be the word for no, regardless of which god you ask. You then know the word for yes, the word for no, and which god is which. Number of questions, minimum 3, maximum infinity. Minimum: you start at God A and ask the sky blue, rock red question, and if you're lucky that's the random god and he's changed from yes to no.

[Trebla]

This doesn't work.

"If I asked you if B was random would you say "ja"?". If he answers "ja" that means either B is random or A is" - ja could mean no in his language. You don't know if it's yes or no he has replied.

It doesn't matter if "ja" is yes or no... the answer will be the same, that's the point of the level of abstraction. As for your suggestion, you gave six questions in your example and assumed the random god would change his answer... which he may or may not do. You can't assume he will.

[quote=Mike-I"]
I would say it's not 'easy' since a number of people have come to this thread claiming it's impossible for one wrong reason or another.
[/quote]

Ok, let's assume it is impossible when you don't know the words ahead of time. The new exercise becomes what strategy can you come up with to maximize the probability you can identify all three gods." I can get to 5/6 pretty easily, I assume that can be improved upon.

[mike-l]

Ok, let's assume it is impossible when you don't know the words ahead of time. The new exercise becomes what strategy can you come up with to maximize the probability you can identify all three gods." I can get to 5/6 pretty easily, I assume that can be improved upon.

Interesting. What are the rules, do I have to know I'm right, or do I just ask 3 questions and make a guess and have to maximize the chances of winning?

[Pelli]

Didn't Nitrodon prove it's impossible when you don't know the words ahead of time?

Spoiler:

About the second case:
The first answer gives no information beyond identifying one word for yes or no. The yes/no words can be described as "the answer given to the first question" and "the answer not given to the first question", and reducing them to these labels does not remove any information. Since you know what the answer to the first question will be under these labels, you get 0 bits of information from it.

I.e. there are only four different sets of responses:
AAA, AAB, ABA, ABB
where A denotes the response to the first question.

[lordatog]

I don't believe that argument is correct. The first question may not provide us with any immediate information, but we may learn enough from the other two questions to go back and interpret that first answer. Suppose my first question is asked to A, and goes "Is exactly one of the following true: B is random, or you tell the truth?" The answer I receive is "Lum." At the time, all I learn is that Lum is one of the words. If I later learn that "Lum" means "yes", however, then that previously worthless answer now tells me that B is not random.

[jestingrabbit]

That's not a great example. We usually consider random to mean "answering in a manner that has no regard for the question whatsoever" but I do take your point.

I, however, suspect that nitrodon is correct unless we allow a cheat. The information theoretic perspective works fine I think but my cheat would be

Spoiler:

to distinguish the answers using the alphabetical order of their transliterations. Of course, if the answers are in terms of the way the wind blows or something equally bizarre, then this would of course fail, and anyway I do consider it a cheat.

[Token]

That's not a great example. We usually consider random to mean "answering in a manner that has no regard for the question whatsoever" but I do take your point.

How is the definition of random relevant to lordatog's example? I don't see it.

[jestingrabbit]

Good point. It seemed like it would rely on that and I lazily failed to check.

[Trebla]

Interesting. What are the rules, do I have to know I'm right, or do I just ask 3 questions and make a guess and have to maximize the chances of winning?

I would say maximize your chances of being certain given all possible configurations.

Example scenario:
1) To God A: Is 1=1?
2) To God A: Is 1=1?

If God A is the truthteller, he'll give the same answer twice
If God A is the liar, he'll give the same answer twice
If God A is the Random. He has a 50% chance of giving the same answer twice, 50% chance of switching (roughly).

If he switches and you identify him as the random god, you can then figure the other two out with the abstraction... "if I asked you if you were the truthteller, would you answer <one of the words used>?"

In this scenario, you will have a solution 1/6 of the time. (1/3 of the time you'll ask Random God, and 1/2 of that time you'll learn which God he is).

It would be interesting to see if we approach a 100% solution.

Edit: I'm leaning towards impossible, but don't have the background to prove it. The way I see it is you can only risk asking the random God one question (which must be your first question) to keep your solution set within the 8 possible permutations (AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB) if a second question is directed at a God which you must allow for the possibility of being Random you'll have at least two of those possible answer sets doubled. So it's imperative that you identify a non-Random God on the first question (as the classical answer demonstrates) which I don't see a way to do while the words are unknown.