Is This Even Possible?

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

theseum
Posts: 1
Joined: Wed Dec 16, 2009 10:11 pm UTC

Is This Even Possible?

Postby theseum » Wed Dec 16, 2009 10:18 pm UTC

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
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Is This Even Possible?

Postby Token » Thu Dec 17, 2009 12:45 am UTC

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.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Is This Even Possible?

Postby Nitrodon » Thu Dec 17, 2009 1:30 am UTC

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.

User avatar
TheGrammarBolshevik
Posts: 4878
Joined: Mon Jun 30, 2008 2:12 am UTC
Location: Going to and fro in the earth, and walking up and down in it.

Re: Is This Even Possible?

Postby TheGrammarBolshevik » Thu Dec 17, 2009 4:36 am UTC

Isn't the second case just the same as this (Spoiler note: The solution is on that page, a little ways down)?
Nothing rhymes with orange,
Not even sporange.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Is This Even Possible?

Postby jestingrabbit » Thu Dec 17, 2009 3:41 pm UTC

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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Fat Pigeon
Posts: 7
Joined: Tue Jul 15, 2008 3:06 am UTC

Re: Is This Even Possible?

Postby Fat Pigeon » Mon Dec 21, 2009 8:02 am UTC

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.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Is This Even Possible?

Postby jestingrabbit » Mon Dec 21, 2009 8:22 am UTC

Fat Pigeon wrote: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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Zetetic1123
Posts: 7
Joined: Sat Dec 19, 2009 10:12 pm UTC

Re: Is This Even Possible?

Postby Zetetic1123 » Mon Dec 21, 2009 9:48 pm UTC

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
Posts: 615
Joined: Tue Nov 27, 2007 7:29 pm UTC

Re: Is This Even Possible?

Postby Puck » Mon Dec 21, 2009 10:09 pm UTC

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.
22/7 wrote:If I could have an alternate horn that would yell "If you use your turn signal, I'll let you in" loud enough to hear inside another car, I would pay nearly any amount of money for it.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Is This Even Possible?

Postby mike-l » Tue Dec 22, 2009 6:01 pm UTC

Puck wrote: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)
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

akashra
Posts: 503
Joined: Tue Jan 01, 2008 6:54 am UTC
Location: Melbourne, AU
Contact:

Re: Is This Even Possible?

Postby akashra » Sun Dec 27, 2009 11:03 pm UTC

TheGrammarBolshevik wrote: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.
( find / -name \*base\* -exec chown us : us { } \ ; )

ARandomDude
Posts: 60
Joined: Mon Dec 28, 2009 7:10 pm UTC

Re: Is This Even Possible?

Postby ARandomDude » Mon Dec 28, 2009 7:13 pm UTC

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?

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Is This Even Possible?

Postby jestingrabbit » Tue Dec 29, 2009 4:48 am UTC

ARandomDude wrote: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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Isvan
Posts: 18
Joined: Wed Jan 13, 2010 8:03 pm UTC

Re: Is This Even Possible?

Postby Isvan » Thu Jan 14, 2010 1:52 pm UTC

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

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Is This Even Possible?

Postby jestingrabbit » Thu Jan 14, 2010 2:10 pm UTC

Isvan wrote:
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".
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
undecim
Posts: 289
Joined: Tue Jan 19, 2010 7:09 pm UTC
Contact:

Re: Is This Even Possible?

Postby undecim » Sat Jan 23, 2010 1:37 am UTC

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.
Blue, blue, blue

lordatog
Posts: 84
Joined: Tue Feb 10, 2009 5:09 am UTC

Re: Is This Even Possible?

Postby lordatog » Sat Jan 23, 2010 7:33 am UTC

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
Posts: 3
Joined: Mon Apr 13, 2009 7:28 pm UTC

Re: Is This Even Possible?

Postby Comm » Mon Jan 25, 2010 12:06 am UTC

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
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: Is This Even Possible?

Postby Nitrodon » Mon Jan 25, 2010 12:24 am UTC

Comm wrote: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
Posts: 3
Joined: Sat Feb 06, 2010 4:50 am UTC

Re: Is This Even Possible?

Postby Davecom3 » Sun Feb 07, 2010 3:09 am UTC

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.

User avatar
NumberFourtyThree
Posts: 26
Joined: Sun Feb 21, 2010 7:00 am UTC
Location: Too many to list here, due to a cloning accident.

Re: Is This Even Possible?

Postby NumberFourtyThree » Sun Feb 21, 2010 8:06 am UTC

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.
The world is imperfect because it has to be. If everything were perfectly fair and without problems we would all live the exact same pointless life, with no possible meaning to it.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Is This Even Possible?

Postby mike-l » Tue Feb 23, 2010 7:58 pm UTC

NumberFourtyThree wrote:<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.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

reffu
Posts: 11
Joined: Thu Feb 25, 2010 5:42 am UTC

Re: Is This Even Possible?

Postby reffu » Thu Feb 25, 2010 6:15 am UTC

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.
"With great power comes bigger batteries and longer recharge times"

lordatog
Posts: 84
Joined: Tue Feb 10, 2009 5:09 am UTC

Re: Is This Even Possible?

Postby lordatog » Fri Feb 26, 2010 3:52 am UTC

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
Posts: 1
Joined: Thu Apr 01, 2010 9:36 pm UTC

Re: Is This Even Possible?

Postby clickz » Thu Apr 01, 2010 9:47 pm UTC

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

User avatar
tastelikecoke
Posts: 1208
Joined: Mon Feb 01, 2010 7:58 am UTC
Location: Antipode of Brazil
Contact:

Re: Is This Even Possible?

Postby tastelikecoke » Mon Apr 05, 2010 4:11 am UTC

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
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: Is This Even Possible?

Postby redrogue » Thu Apr 08, 2010 4:45 pm UTC

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.
Is 'no' your answer to this question?

Trebla
Posts: 373
Joined: Fri Apr 02, 2010 1:51 pm UTC

Re: Is This Even Possible?

Postby Trebla » Mon Apr 12, 2010 1:00 pm UTC

mike-l wrote:
NumberFourtyThree wrote:<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
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Is This Even Possible?

Postby mike-l » Mon Apr 12, 2010 6:02 pm UTC

Trebla wrote: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.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Trebla
Posts: 373
Joined: Fri Apr 02, 2010 1:51 pm UTC

Re: Is This Even Possible?

Postby Trebla » Tue Apr 13, 2010 2:52 pm UTC

mike-l wrote: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
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Is This Even Possible?

Postby mike-l » Tue Apr 13, 2010 5:51 pm UTC

Trebla wrote: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.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

dawolf
Posts: 164
Joined: Thu Jan 07, 2010 9:21 pm UTC

Re: Is This Even Possible?

Postby dawolf » Tue Apr 13, 2010 7:15 pm UTC

NumberFourtyThree wrote:
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
Posts: 373
Joined: Fri Apr 02, 2010 1:51 pm UTC

Re: Is This Even Possible?

Postby Trebla » Tue Apr 13, 2010 7:57 pm UTC

dawolf wrote: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
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Is This Even Possible?

Postby mike-l » Tue Apr 13, 2010 8:33 pm UTC

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?
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

Pelli
Posts: 22
Joined: Fri Jun 26, 2009 6:02 am UTC

Re: Is This Even Possible?

Postby Pelli » Tue Apr 13, 2010 8:39 pm UTC

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

Spoiler:
Nitrodon wrote: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
Posts: 84
Joined: Tue Feb 10, 2009 5:09 am UTC

Re: Is This Even Possible?

Postby lordatog » Tue Apr 13, 2010 9:13 pm UTC

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.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Is This Even Possible?

Postby jestingrabbit » Tue Apr 13, 2010 9:23 pm UTC

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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

Re: Is This Even Possible?

Postby Token » Tue Apr 13, 2010 9:31 pm UTC

jestingrabbit wrote: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.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Is This Even Possible?

Postby jestingrabbit » Tue Apr 13, 2010 10:03 pm UTC

Good point. It seemed like it would rely on that and I lazily failed to check.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Trebla
Posts: 373
Joined: Fri Apr 02, 2010 1:51 pm UTC

Re: Is This Even Possible?

Postby Trebla » Wed Apr 14, 2010 1:56 pm UTC

mike-l wrote: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.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 5 guests