Is This Even Possible?

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

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

Re: Is This Even Possible?

Postby Pelli » Wed Apr 14, 2010 2:33 pm UTC

lordatog wrote: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.


What I'm saying is that any deterministic algorithm will be of the following form (in PHP):
Spoiler:

Code: Select all

//ask($person, $question) means ask $question to $person
//All other functions (names without $ prefix) are predefined
//No variable is predefined
$question1 = predefined_question();
$person1 = predefined_person();
$answer1 = ask($person1, $question1);

$question2 = a_question_that_can_make_use_of_the_word($answer1);
$person2 = predefined_person_2();
$answer2 = ask($person2, $question2);

if($answer1 == $answer2) {
   $question3 = another_question_that_can_make_use_of_the_word($answer1);
   $person3 = person_to_ask_if_answer1_equals_answer2();
   $answer3 = ask($person3, $question3);
   if($answer3 == $answer1) echo "Case 1!"; else echo "Case 2!";
} else {
   $question3 = a_question_that_can_make_use_of_the_words($answer1, $answer2);
   $person3 = person_to_ask_if_answer1_differs_from_answer2();
   $answer3 = ask($person3, $question3);
   if($answer3 == $answer1) echo "Case 3!"; else echo "Case 4!";
}


This can only yield 4 different answers, so it can't solve the problem completely.
Last edited by Pelli on Wed Apr 14, 2010 9:21 pm UTC, edited 1 time in total.

redrogue
Posts: 116
Joined: Tue Dec 15, 2009 9:17 pm UTC

Re: Is This Even Possible?

Postby redrogue » Wed Apr 14, 2010 3:29 pm UTC

lordatog wrote: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.


Except you are upping the amount of information you need out of the other two questions. I don't believe you need to actually know what the words for 'yes' and 'no' are to solve the puzzle.
Is 'no' your answer to this question?

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

Re: Is This Even Possible?

Postby Token » Wed Apr 14, 2010 4:11 pm UTC

To add to the above: if I learn subsequently that the answer to the first question was the word for "yes", then I must have expended a bit of information to do so. To learn what the word for "yes" is, I must ask a question to which I *know* the answer will be the word for "yes" (or "no", of course). Therefore, I get no information from that question beyond the translations of the words.

As some more general advice - if you have both a proof and a counterexample to something, it is always a good idea to run through the steps of the proof with the counterexample in mind to see which breaks down.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

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

Re: Is This Even Possible?

Postby Token » Wed Apr 14, 2010 4:23 pm UTC

mike-l wrote:Since there are six sequences of responses that are not all the same, and there are six arrangements of gods, it's not necessarily impossible just by counting this way.

What? There are six arrangements of gods, yes, but only four distinguishability-classes of sequences of responses. The problem is unsolvable, even without the hurdle of the random god.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

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

Re: Is This Even Possible?

Postby lordatog » Wed Apr 14, 2010 4:24 pm UTC

redrogue wrote:
lordatog wrote: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.


Except you are upping the amount of information you need out of the other two questions. I don't believe you need to actually know what the words for 'yes' and 'no' are to solve the puzzle.


You don't need to know what the words mean, at least in the version where you know what the words are to begin with. It was just an example of how to get information out of the first question. There are twelve possible states at first. A, B, and C can be truth, lies, and random in any order (6 possibilities) and the two words could mean "yes" or "no" in either order, doubling that count. If you ask your first question as I describe, you have ruled out four of those twelve states: (A true, B random, C false, Lum = yes), (A false, B random, C true, Lum = yes), (A true, B false, C random, Lum = no), (A false, B true, C random, Lum = no). That's certainly better than getting zero bits out of the question. I do not claim that asking this question leads to a solution - like most people in this thread, I believe the problem as stated to be impossible. I just don't think that anyone has yet found a successful proof of that.

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

Re: Is This Even Possible?

Postby mike-l » Wed Apr 14, 2010 4:30 pm UTC

Token wrote:
mike-l wrote:Since there are six sequences of responses that are not all the same, and there are six arrangements of gods, it's not necessarily impossible just by counting this way.

What? There are six arrangements of gods, yes, but only four distinguishability-classes of sequences of responses. The problem is unsolvable, even without the hurdle of the random god.


There are 8 distinguishable sequences if you put an order on the language. I posted above (in an edit to the quoted post) what I think is a solution when random has to answer either truthfully/falsely, so he must answer No to Are you lying, for example.

EDIT:
Proposed solution moved to this post:

I think I have a solution. It depends on any two words being comparable, which is fine if their language has a finite alphabet, which I think is reasonable, and in the case where random answers each question either truthfully or falsely, but does not answer randomly.

Spoiler:
Call the gods A,B,C.

Ask god A: "If I asked you if B were random, would your answer be first among the words for yes/no?"
Ask god B: "If I asked you if you were the truth teller, would your answer be first among the words for yes/no?"

Now, If their answers are different, then you know which word is first, you have truthful answers to both those questions and so you know which god B is. You can now use your third question on any god to identify C (or A) out of the remaining two.

If their answers are the same, the answer given must be the later word and B must be a liar, since if the answer were the first word, B would be both random and the truthteller. Again, use your third question to figure out the identity of C.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

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

Re: Is This Even Possible?

Postby Token » Wed Apr 14, 2010 4:59 pm UTC

mike-l wrote:There are 8 distinguishable sequences if you put an order on the language. I posted above (in an edit to the quoted post) what I think is a solution when random has to answer either truthfully/falsely, so he must answer No to Are you lying, for example.

Ah, OK. Your original post made it less clear that you were solving a completely different problem. I'd complain, but my own sig would make me a hypocrite. :D

lordatog wrote:You don't need to know what the words mean, at least in the version where you know what the words are to begin with. It was just an example of how to get information out of the first question. There are twelve possible states at first. A, B, and C can be truth, lies, and random in any order (6 possibilities) and the two words could mean "yes" or "no" in either order, doubling that count. If you ask your first question as I describe, you have ruled out four of those twelve states: (A true, B random, C false, Lum = yes), (A false, B random, C true, Lum = yes), (A true, B false, C random, Lum = no), (A false, B true, C random, Lum = no). That's certainly better than getting zero bits out of the question. I do not claim that asking this question leads to a solution - like most people in this thread, I believe the problem as stated to be impossible. I just don't think that anyone has yet found a successful proof of that.

Emphasis mine. If you don't think Nitrodon's proof works, at which step does his reasoning fail?
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

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

Re: Is This Even Possible?

Postby lordatog » Wed Apr 14, 2010 5:12 pm UTC

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.


It is verifiably possible to rule out at least 4 of 12 possibilities with your first question, so the conclusion that you get 0 bits of information is obviously incorrect. I admit I don't know which part of his argument doesn't work, though. I suspect it has to do with his labeling of the answers, in particular the fact that labeling them in this way causes their identities to be dependant on what your first question is.

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

Re: Is This Even Possible?

Postby Token » Wed Apr 14, 2010 5:16 pm UTC

If you include the meaning of the first answer as one of the states you are distinguishing against, then you are trying to distinguish between 12 states with 3 questions, which is immediately impossible without considering any of the other specifics of the problem.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

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

Re: Is This Even Possible?

Postby mike-l » Wed Apr 14, 2010 5:16 pm UTC

If you don't think Nitrodon's proof works, at which step does his reasoning fail?


Sorry, which is Nitrodon's proof? That you gain 0 bits of information from the first question if you don't know the words ahead of time?

The problem with this is that you may subsequently get information that makes the first question give information. Obviously figuring out a word for yes or no would do this, but then you've increased the amount of knowledge you need from 1/6 to 1/12 possibilities, so even with 8 bits you still come up short. But for this proof to be complete, you need to prove that without knowing a word for yes or no, you can't ask a question that will become meaningful later without discovering the words for yes and no.

In my previous post, I suggested that you could ask 'would you answer with the word for yes/no that appears first alphabetically', which is seemingly a counterexample to the proof.

Furthermore, questions such as that become meaningful as soon as you've heard 2 answers, and there are 6 combinations that give 2 answers (8 total combinations, 2 of which are all one answer), so if you can find a sequence of questions that guarantees 2 answers, you might even be able to solve the 'hardest' version of this puzzle with questions like the above (Hardest version being you don't know the words for yes/no ahead of time and random answers randomly yes/no, with no regard to the question)

As it stands, I posted a solution for the 2nd hardest version (you don't know the words ahead of time, but random is randomly true or false) and await feedback.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

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

Re: Is This Even Possible?

Postby Trebla » Wed Apr 14, 2010 5:54 pm UTC

mike-l wrote:
Spoiler:
Call the gods A,B,C.

Ask god A: "If I asked you if B were random, would your answer be first among the words for yes/no?"
Ask god B: "If I asked you if you were the truth teller, would your answer be first among the words for yes/no?"

Now, If their answers are different, then you know which word is first, you have truthful answers to both those questions and so you know which god B is. You can now use your third question on any god to identify C (or A) out of the remaining two.

If their answers are the same, the answer given must be the later word and B must be a liar, since if the answer were the first word, B would be both random and the truthteller. Again, use your third question to figure out the identity of C.


Counter-example.

God A is truthteller
God B is random

Words are "Asi" and "No"

Answer to question 1: Asi (Answering honestly that B is random)
Answer to question 2: Asi (Randomly choosing to lie in the internal question, then tell the truth in the external question)

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

Re: Is This Even Possible?

Postby mike-l » Wed Apr 14, 2010 7:06 pm UTC

Trebla wrote:Answer to question 2: Asi (Randomly choosing to lie in the internal question, then tell the truth in the external question)


Sorry, I should clarify random god's behaviour further as: Before each question is asked he flips a coin and answers the entire question truthfully if he got heads or the entire question falsely if he got tails. (See for example http://en.wikipedia.org/wiki/The_Hardes ... uzzle_Ever which describes the same problem when you do know the words ahead of time)

Edit:

To further alleviate ambiguity, the questions should be changed from "If I asked you X, would you answer..." to "If I asked someone X, and they chose to answer the same way you are choosing to answer this question, would they answer"
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

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

Re: Is This Even Possible?

Postby Trebla » Wed Apr 14, 2010 8:06 pm UTC

That seems a good solution with the given premise. My initial 5/6 solution was very similar.

Spoiler:
1) To God A: Is the word for "yes" alphabetically before the word for "no"
2) To God A: Is the word for "no" alphabetically before the word for "yes"

a) In 1/3 of the cases, you will ask the truthteller. He will always give the alphabetically first answer first.
b) In 1/3 of the cases, you will ask the liar. He will always give the alphabetically second answer first.
c) In 1/3 of the cases, you will ask random:
c1) In 1/2 of those cases (on average), he will give the same answer twice, identifying himself as random
c2) In 1/2 of those cases (on average), he will switch answers and you will be stuck

In a) or b), you clearly identify the truthteller or liar and can ask a third question abstractly to identify the other two
In c1) you have identified random, and can ask either God B or God C a question abstractly to identify both
In c2) (which will be the case 1/6 of the time) you can not make progress and fail to solve.

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

Re: Is This Even Possible?

Postby Token » Wed Apr 14, 2010 8:28 pm UTC

mike-l wrote:The problem with this is that you may subsequently get information that makes the first question give information. Obviously figuring out a word for yes or no would do this, but then you've increased the amount of knowledge you need from 1/6 to 1/12 possibilities, so even with 8 bits you still come up short. But for this proof to be complete, you need to prove that without knowing a word for yes or no, you can't ask a question that will become meaningful later without discovering the words for yes and no.

If instead of concluding that the first question gave no bits of information, the proof concluded that the number of bits of information you got was always one less than the number of questions you asked, what would then be your problem with it? Let's assume that you have no way of choosing one word over the other beyond their frequency and arrangement in the sequence of answers you receive (or any better condition you can think of that in that vein).
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

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

Re: Is This Even Possible?

Postby mike-l » Wed Apr 14, 2010 8:51 pm UTC

Token wrote:If instead of concluding that the first question gave no bits of information, the proof concluded that the number of bits of information you got was always one less than the number of questions you asked, what would then be your problem with it? Let's assume that you have no way of choosing one word over the other beyond their frequency and arrangement in the sequence of answers you receive.


If the proof concluded that 3 questions only yielded 2 bits, I would agree it's impossible, but it doesn't conclude that (correctly at least).

If it is the case that there is no way of choosing one word over the other (say, he makes up the word for yes the first time he has to answer yes, and same for no, so he can't compare the words at all), then I would guess again that this is impossible to do in 3 questions, but you need a proof that this is the case, and no such proof has been put forward yet. But furthermore, this is yet another problem.

Is there anything wrong with my posted solution to the case of {You do not know the words ahead of time, Random's answers in each round are either entirely true or entirely false}?
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

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

Re: Is This Even Possible?

Postby Token » Wed Apr 14, 2010 9:31 pm UTC

mike-l wrote:If the proof concluded that 3 questions only yielded 2 bits, I would agree it's impossible, but it doesn't conclude that (correctly at least).

I'll try and rephrase in an entirely unambiguous way: if we took Nitrodon's proof, and replaced the assertion that [the first question gives no information] to one that [n questions gives n-1 bits of information], we would end up with a proof (correct or not) that circumvents your maybe-we-can-get-information-from-the-first-question-after-all "objection". You are asserting that this proof is incorrect. In the interest of having something concrete to debate, what specific reason makes you say this? I've looked through the thread for a specific objection, but if there is one I've missed it.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

Valiance
Posts: 1
Joined: Wed Apr 14, 2010 11:07 pm UTC

Re: Is This Even Possible?

Postby Valiance » Wed Apr 14, 2010 11:50 pm UTC

I'm pretty sure you can do it in 4. (Whether the random demon answers truly randomly or not)

Spoiler:
1. {To any Demon} If I asked the other demons a single identical question, would they both give me the same answer?
2. If you did not get an answer, ask the same question of another demon. At this point, you know which demon is random.

(Only the demon who answers randomly could answer this question (Even if a demon knows the other demons answer to every question, he cannot know what question you will ask). If you get an answer, you know this is the random demon.)

3. Ask one of the non-random demons 'Are you a liar'. The answer will be the word for no.

The situation then simplifies to the standard two-demon problem, which can be solved with one question.


This method would break down if the demons knew whether the random demon was going to answer truthfully falsely for each question though... (But then the problem statement should probably read that random answers in a 'randomly predetermined sequence')


I guess this is pretty much summed up in that wiki article. It says something about a two-question solution near the end, but I haven't been able to put it together.

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

Re: Is This Even Possible?

Postby mike-l » Thu Apr 15, 2010 12:40 am UTC

Token wrote:
mike-l wrote:If the proof concluded that 3 questions only yielded 2 bits, I would agree it's impossible, but it doesn't conclude that (correctly at least).

I'll try and rephrase in an entirely unambiguous way: if we took Nitrodon's proof, and replaced the assertion that [the first question gives no information] to one that [n questions gives n-1 bits of information], we would end up with a proof (correct or not) that circumvents your maybe-we-can-get-information-from-the-first-question-after-all "objection". You are asserting that this proof is incorrect. In the interest of having something concrete to debate, what specific reason makes you say this? I've looked through the thread for a specific objection, but if there is one I've missed it.


So you are asking what the problem is with the proof "N questions gives N-1 bits of information. Since 2^(3-1) < 6 you cannot distinguish 6 possibilities with only 3 questions"?

My objection is that N questions gives N-1 bits of information is not true.

It's not true when you know the words ahead of time, because you can use one of the words in the questions themselves to 'fake' a translation.
It's not true (seemingly) if the words are chosen ahead of time but unknown to you, and chosen from a set in which there is some way of comparing any two elements (eg a finite alphabet). See my posts.

What argument is there that adding some more restrictions makes it true, other than 'proof by lack of imagination'?
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

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 Apr 15, 2010 2:30 am UTC

mike-l wrote:What argument is there that adding some more restrictions makes it true, other than 'proof by lack of imagination'?


Nitrodon's. If the words are incomparable, like the rumble of thunder and the the smell of flowers, then the first answer is just the first answer. It can't be related to the other possible answer in any way, and so there are only the four possible sequences of responses as described by nitrodon.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

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

Re: Is This Even Possible?

Postby mike-l » Thu Apr 15, 2010 4:30 am UTC

jestingrabbit wrote:
mike-l wrote:What argument is there that adding some more restrictions makes it true, other than 'proof by lack of imagination'?


Nitrodon's. If the words are incomparable, like the rumble of thunder and the the smell of flowers, then the first answer is just the first answer. It can't be related to the other possible answer in any way, and so there are only the four possible sequences of responses as described by nitrodon.


If I can communicate arbitrarily large amounts of information in my question, I can use the axiom of choice to make ANY two responses comparable. In the original question you were familiar with the language but unsure of the exact meaning of words, certainly in this case any two responses are comparable.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

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

Re: Is This Even Possible?

Postby Token » Thu Apr 15, 2010 8:21 am UTC

mike-l wrote:So you are asking what the problem is with the proof "N questions gives N-1 bits of information. Since 2^(3-1) < 6 you cannot distinguish 6 possibilities with only 3 questions"?

Have you read Nitrodon's post? Like, at all?
My objection is that N questions gives N-1 bits of information is not true.

It's not true when you know the words ahead of time, because you can use one of the words in the questions themselves to 'fake' a translation.
It's not true (seemingly) if the words are chosen ahead of time but unknown to you, and chosen from a set in which there is some way of comparing any two elements (eg a finite alphabet). See my posts.

So, your objection is that it's not true if you drop either of two assumptions I've been fairly explicit about making?
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

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

Re: Is This Even Possible?

Postby mike-l » Thu Apr 15, 2010 1:16 pm UTC

Token wrote:
mike-l wrote:So you are asking what the problem is with the proof "N questions gives N-1 bits of information. Since 2^(3-1) < 6 you cannot distinguish 6 possibilities with only 3 questions"?

Have you read Nitrodon's post? Like, at all?

Yes, Nitrodon's proof requires further assumptions to be correct. He makes an argument that there are only 4 classes of responses when you don't know the words. This isn't true if you can put an order on the possible responses (which, if we can communicate large (read: infinite) amounts of information in our question, and accept the axiom of choice, we can ALWAYS do, but we also can also obviously do with any known human language, by asking for the first word to appear alphabetically in the english spelling of the word). You then made the assumption (which I missed/misinterpretted/forgot) that the words are incomparable. In this case, I agree it's a correct proof under the given assumptions. But I think you've just gone and assumed what you were trying to prove.


My objection is that N questions gives N-1 bits of information is not true.

It's not true when you know the words ahead of time, because you can use one of the words in the questions themselves to 'fake' a translation.
It's not true (seemingly) if the words are chosen ahead of time but unknown to you, and chosen from a set in which there is some way of comparing any two elements (eg a finite alphabet). See my posts.

So, your objection is that it's not true if you drop either of two assumptions I've been fairly explicit about making?[/quote]
Sorry, I did misread(or just forget) your post where you made the assumption that there is no way to compare the words.

However, I'd say it's not very interesting to have a puzzle thread where we are essentially saying
"Ok, here's a puzzle, it's hard can you solve it?"
'Here's a solution'
"Ok, assume you can't do that"
'Ok, here's another solution not doing that'
"Ok, now assume it's impossible"
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

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

Re: Is This Even Possible?

Postby Token » Thu Apr 15, 2010 2:19 pm UTC

Well, really, I'm not asking you to assume something's impossible; I'm asking you to stop assuming that it is. It's unreasonable to assume that we have in advance a function to distinguish between two words in a language we're told we don't understand for the same reason (though yes, slightly less extreme) that's it's unreasonable to assume that we can look up the identities of the gods on Wikipedia without asking a single question: it's outside the scope of the problem. To make these problems interesting, we have to agree to make only the minimal assumptions necessary to ensure that the problem is well-formed. Adding assumptions can certainly be interesting, but just realize that *you* are the one using a variant of the original puzzle.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

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

Re: Is This Even Possible?

Postby mike-l » Thu Apr 15, 2010 2:41 pm UTC

Token wrote:Well, really, I'm not asking you to assume something's impossible; I'm asking you to stop assuming that it is. It's unreasonable to assume that we have in advance a function to distinguish between two words in a language we're told we don't understand for the same reason (though yes, slightly less extreme) that's it's unreasonable to assume that we can look up the identities of the gods on Wikipedia without asking a single question: it's outside the scope of the problem. To make these problems interesting, we have to agree to make only the minimal assumptions necessary to ensure that the problem is well-formed. Adding assumptions can certainly be interesting, but just realize that *you* are the one using a variant of the original puzzle.


My point is that there are circumstances in which the original problem is solvable, for example when their language uses a known finite alphabet (for example the standard abc that's used by a very large portion of the world, and an even bigger portion of the world can be written in). Perhaps there are other easier or broader applying ways to distinguish words that we haven't come up with yet. Noone has offered any proof that this isn't the case, we're just assuming it's not. (and like I said, given the axiom of choice and the ability to communicate infinite amounts of information in your questions, it's ALWAYS possible. Such a solution would hardly be unprecedented on these boards.. infinite hats for example)
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

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

Re: Is This Even Possible?

Postby Trebla » Thu Apr 15, 2010 2:47 pm UTC

jestingrabbit wrote:Nitrodon's. If the words are incomparable, like the rumble of thunder and the the smell of flowers, then the first answer is just the first answer. It can't be related to the other possible answer in any way, and so there are only the four possible sequences of responses as described by nitrodon.


This is another way to add abstraction that is simplified by comparing the two words alphabetically. Any two things are comparable if you find the right way to compare them.

These are Gods, by traditional definition they are omniscient. We can remove that assumption and invalidate this solution if you like, but allowing the words to be comparable seems vital. Replace the phrase "the word that comes alphabetically first" with "the answer I would find more aesthetically pleasing" or "if I were to phonetically spell them, the one that would come alphabetically first." Even though you may not know which is more pleasing ahead of time (or which would be spelled first), the Gods know which you would find more so, and after receiving both answers, you will then know.

To add to the other discussion. You only need two pieces of information to solve the puzzle. You need the identity of two Gods. The third one is then self-evident. If after two questions, you can correctly identify any single God, you can solve the puzzle on the third.

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

Re: Is This Even Possible?

Postby mike-l » Thu Apr 15, 2010 3:14 pm UTC

Trebla wrote:To add to the other discussion. You only need two pieces of information to solve the puzzle. You need the identity of two Gods. The third one is then self-evident. If after two questions, you can correctly identify any single God, you can solve the puzzle on the third.


Well... yes, but the identity of the first god is 1 of 3 possibilities, so the identity of one god cannot be ascertained by a question with only 2 responses. No matter how you cut it, you need to distinguish between 1 of 6 possibilities, which means the problem is only solvable if you can distinguish at least 6 different answer sequences. Known words have 8 sequences, comparable words have 7 (since yes yes yes and no no no look the same), completely incomparable words have 4, so the first 2 situations are solvable (and solutions have been posted) and the last is not.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

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

Re: Is This Even Possible?

Postby Trebla » Thu Apr 15, 2010 8:18 pm UTC

mike-l wrote: Known words have 8 sequences, comparable words have 7 (since yes yes yes and no no no look the same), completely incomparable words have 4, so the first 2 situations are solvable (and solutions have been posted) and the last is not.


Does the second scenario (unknown, comparable words) have a posted solution when the random god answers truly randomly? Did I skim over it?

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

Re: Is This Even Possible?

Postby mike-l » Fri Apr 16, 2010 4:05 am UTC

Trebla wrote:
mike-l wrote: Known words have 8 sequences, comparable words have 7 (since yes yes yes and no no no look the same), completely incomparable words have 4, so the first 2 situations are solvable (and solutions have been posted) and the last is not.


Does the second scenario (unknown, comparable words) have a posted solution when the random god answers truly randomly? Did I skim over it?


No. I don't believe this to be possible but don't have a proof.
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 » Fri Apr 16, 2010 11:47 am UTC

Proof of impossibility for unknown comparable words with random answering yes/no randomly:
Spoiler:
Let the words for yes and no be X < Y. There are eight answer strings, out of which two are indistinguishable: XXX=YYY. These must be assigned to 6 cases.

There is nothing to compare the first answer to, so it cannot help in choosing which daemon to ask the next question to. Hence it is predetermined which two daemons will be asked first.

If two different daemons A,B are asked:
At least two different answer strings must be assigned to the case (A,B,C) = (Random,Truth,Lie) since A might answer either way on the first question. Similarly, each other case where A or B is Random must also be assigned at least two strings. Finally, the cases where C is Random need at least one string each. All in all, 4x2 + 2 = 10 strings. This won't work.

If the same daemon A is asked twice:
After two questions, there are three distinguishable responses: XY, YX, XX=YY. There is always the risk that A is random, so each of the three cases must take care of both (R,T,L) and (R,L,T). This will fill up all possibilities for XY (which can become either XYX or XYY) and YX (similar) and two of the possibilities for XX=YY (which can become XXY, YYX, or XXX=YYY). There will be just one answer string left for the 4 cases where A is not Random. This won't work either.

QED.

User avatar
Lenoxus
Posts: 120
Joined: Thu Jan 06, 2011 11:14 pm UTC

Re: Is This Even Possible?

Postby Lenoxus » Tue Feb 14, 2012 7:53 pm UTC

Pelli wrote:Proof of impossibility for unknown comparable words with random answering yes/no randomly:
Spoiler:
Let the words for yes and no be X < Y. There are eight answer strings, out of which two are indistinguishable: XXX=YYY. These must be assigned to 6 cases.

There is nothing to compare the first answer to, so it cannot help in choosing which daemon to ask the next question to. Hence it is predetermined which two daemons will be asked first.

If two different daemons A,B are asked:
At least two different answer strings must be assigned to the case (A,B,C) = (Random,Truth,Lie) since A might answer either way on the first question. Similarly, each other case where A or B is Random must also be assigned at least two strings. Finally, the cases where C is Random need at least one string each. All in all, 4x2 + 2 = 10 strings. This won't work.

If the same daemon A is asked twice:
After two questions, there are three distinguishable responses: XY, YX, XX=YY. There is always the risk that A is random, so each of the three cases must take care of both (R,T,L) and (R,L,T). This will fill up all possibilities for XY (which can become either XYX or XYY) and YX (similar) and two of the possibilities for XX=YY (which can become XXY, YYX, or XXX=YYY). There will be just one answer string left for the 4 cases where A is not Random. This won't work either.

QED.


This must be incorrect in some way, because the problem does have a real solution. Part of the trick is to not care which word actually means yes or no; in fact, it certainly is possible that a string of X-X-X will tell you something, and likewise for Y-Y-Y.

Here's a simple thought experiment, where you know that anyone you talk to is either an always-honest knight or an always-dishonest knave, and that they answer in english. Suppose I ask someone the question:

"If I asked you 'Is fire hot?' would you say yes?"

A knight will tell the truth about telling the truth and say yes. A knave will lie about lying and say yes. So what you've actually learned is that fire is hot. Well, that's not necessarily useful, but this principle can easily be extended.

Suppose that you ask: "If I asked you 'Is fire hot?' would you say no?"

Then a knight will tell the truth about telling the truth and say no, while a knave will lie about lying and say no. So now you've learned that it is not the case that fire is not hot, which is to say, that it is hot.

But that's exactly the same thing you learned when you had used "yes" instead of "no". Since "Is fire hot?" was just a placeholder question, we can deduce that it doesn't actually matter which word means "yes" and which means "no"; instead, you only have to pay attention to whether they answered with the same word as the one you had specified.

So if I ask someone "If I asked you 'Do you like anchovies?' would you say bloink?" and the answer is "bloink", then this means that yes, they like anchovies. (You still don't know what "bloink" means, or whether the one you talked to was a knight or a knave.) If the answer is a word other than bloink, that means they don't. Of course, this only works if bloink is in fact a word that either means "yes" or "no". In general, you now have a hack to force anyone consistent to "tell you the truth".

All of the above only works if the person we were talking to was consistently honest or dishonest. A random person is capable of telling the truth about himself lying, or vice-versa. Still, that's not enough to make the problem unsolvable.

The problem description I'm familiar with has "gods" instead of "daemons", so that's the word I'm going to use here. In the official solution (which I admit I did not derive myself), the first question you ask is "Hey, God B: If I asked you 'Is God A Random?', then would you say ja?"

God B's answer will enable you to isolate a non-Random god to talk to next (which is good because consistent gods are easier to deal with). Why?

Well, suppose God B is True. Then an answer of "ja" gives you the information "Yes, God A is Random", while an answer of "da" gives you the information "No, God A is not Random" — regardless of what ja and da actually mean. Or suppose God B is False. Then the exact same thing holds, just as with the anchovies example. So either way, if B is non-Random, then ja means that A is the Random one (and thus C is the other non-Random besides B) while da means that A is the other non-Random.

Finally, suppose that God B is in fact Random. Then his answer will be random, but that doesn't matter; no matter what, your next question will be posed to a different god than God B. This means that no matter what, you will deduce whether or not A is Random. (If A is Random, then it is not possible for B to randomly give a misleading answer — there's only one Random altogether! — and likewise if C is Random.) Then you talk to whichever god you have deduced is non-Random, which might be either A or C. It may well be true that both A and C are non-Random, but all that matters is that you can correctly identify a particular non-Random god.

(As it happens, this principle is also behind the solution to the similar Three Princesses problem, where all you are trying to do is isolate a princess of consistent honesty.)

To the consistent god, you pose the question "If I asked you 'Are you True?', would you answer ja?" If ja means yes, then this god will either tell the truth about telling the truth and say ja, or lie about lying and say da. If ja means no, then he'll either truthfully say ja, or lie and say da. (Try it out with yes and no if you're confused.) You also know that he can't tell the truth about lying or vice versa, because he is definitely not Random. So in short, an answer of ja means he's True, and an answer of da means he's False.

So now you've either isolated that a certain god is True, or that he is False. You only need to ask one more question, which is exactly how many you have left. So you just use the same trick one more time. Ask the same god: "If I asked you 'Is God B Random', would you say ja?" By the same logic as the previous two questions, this non-Random god will be compelled to imply the correct answer, by either saying ja or da. So now you know that
• a certain god (either A or C) is of a certain non-Random nature (either True or False)
• This means that between the other two, B is the Random one (and the other is the "other" one), or B is not the Random one (and the other is Random)
• Plus, thanks to the third question, you do know whether or not B is Random.

So by processes of elimination, you have solved the whole puzzle, even though you still don't know what ja or da means. (In fact, the puzzle should still be solvable even if you only know "ja" or only know "da", without knowing the other word, so long as it is the case that all gods will always, when possible, give an answer that means "yes" or one that means "no".)

For the record, here's a breakdown of which combinations give you which answers, if you always ask using the word ja, and the other word is da.

TFR: D, J, D
FTR: D, D, D
TRF: Either (D, J, J) or (J, D, J)
FRT: Either (D, D, J) or (J, J, J)
RTF: J, D, D
RFT: J, J, D

This covers the 8 possible combinations of Ds and Js, and they are all unique.

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

Re: Is This Even Possible?

Postby mike-l » Tue Feb 14, 2012 9:30 pm UTC

His proof is for the specific case where you can compare the yes no words, but don't know them in advance, and the random god says Yes or No randomly with no regard for the question asked, which just barely slips into the realm of impossibility, any restriction being lessened makes it possible.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
Lenoxus
Posts: 120
Joined: Thu Jan 06, 2011 11:14 pm UTC

Re: Is This Even Possible?

Postby Lenoxus » Tue Feb 14, 2012 10:56 pm UTC

mike-l wrote:His proof is for the specific case where you can compare the yes no words, but don't know them in advance, and the random god says Yes or No randomly with no regard for the question asked, which just barely slips into the realm of impossibility, any restriction being lessened makes it possible.


:oops:

I must have confused Pelli with someone who insisted the original was impossible. Oh well, maybe my comment will help things for someone in a few years from now…

NNikolay
Posts: 3
Joined: Fri May 11, 2012 3:10 am UTC

Re: Is This Even Possible?

Postby NNikolay » Sat Jun 09, 2012 11:08 am UTC

OK, another modification of this puzzle. Basically the same setup with the following assumptions:
1. You can ask paradoxical questions. If god can’t answer Yes or No his head “explodes”. (I saw discussion about this point here. I think this is just matter of clear assumption. Original puzzle was not clear about it. God’s do not “answer” your question with head explosion, so your question can still be called “Yes/No question”.)
2. God’s reply two different unknown words for Yes and No. You can easily tell the difference between words (how can the system with the same word for Yes and No be called “language”?). Head explosion is clearly different from any answer when you see it. But you can’t ask this god second time ;)
3. Random answers randomly Yes or No regardless the question. As a result his head can’t explode.
4. You need solution in two questions.

HonoreDB
Posts: 161
Joined: Tue Feb 06, 2007 4:32 pm UTC
Contact:

Re: Is This Even Possible?

Postby HonoreDB » Mon Jun 11, 2012 11:54 am UTC

NNikolay wrote:OK, another modification of this puzzle.


Spoiler:
Assuming the words are 'da' and 'ja'.

Ask God 1: "Is one of the following true:

You are the liar, and if I were to ask you whether God 2 is the random God you would answer 'da'?
You are the truthteller, and your answer to this question is the God word for 'no'?"

If God 1 answers "da," the possibilities for the three gods are:

liar, random, truth
random, liar, truth
random, truth, liar

So in this case your second question is to God 3. Ask: "Is one of the following true:

You are the truthteller, and if I were to ask you whether God 2 is the random God you would answer 'da'?
You are the liar, and your answer to this question is the God word for 'yes'?"

Da means liar, random, truth.
Ja means random, liar, truth.
<head explodes> means random, truth, liar.

If God 1 answers 'ja', the possibilities are

liar, truth, random
random, liar, truth
random, truth, liar

So an analogous question will narrow it down to one.

If God 1's head explodes, the possibilities are

truth, random, liar
truth, liar, random

So all you have to do is ask a remaining god a paradoxical question and see if its head explodes.

User avatar
t1mm01994
Posts: 299
Joined: Mon Feb 15, 2010 7:16 pm UTC
Location: San Francisco.. Wait up, I'll tell you some tales!

Re: Is This Even Possible?

Postby t1mm01994 » Mon Jun 11, 2012 5:23 pm UTC

HonoreDB wrote:possible solution

Spoiler:
But you don't know the word on beforehand, so you can't assume that you ask for 'da'. You might as well say the word for 'chicken'.

nishank
Posts: 29
Joined: Fri May 11, 2012 9:58 pm UTC

Re: Is This Even Possible?

Postby nishank » Wed Jun 13, 2012 10:55 am UTC

viewtopic.php?f=3&t=273&hilit=gods&start=40
Solved there itself.
No need to know words for true or false, that they are different will do.

nishank
Posts: 29
Joined: Fri May 11, 2012 9:58 pm UTC

Re: Is This Even Possible?

Postby nishank » Wed Jun 13, 2012 11:00 am UTC

Hey guys,
can you give this a read. I think i should have posted it in the logic section
it's a paper on logic i began to write to explain a few things.
i am afraid having a hard time getting the point across. Hoping someone would understand.
viewtopic.php?f=17&t=85957

spelljacker
Posts: 1
Joined: Wed Sep 19, 2012 10:10 pm UTC

Re: Is This Even Possible?

Postby spelljacker » Wed Sep 19, 2012 10:19 pm UTC

From what I can tell, you can't do it with 100% certainty in 3 questions, since it takes a minimum of 2 (at most, 3) just to know what "yes" and "no" are. Some others have posted that isn't necessary, but then how do you know which is the liar and which is always telling the truth?

However, I think I can in 5...though I wouldn't mind if someone else had a look to let me know if I erred.

(and I'm sorry if this is awkward to read, my whiteboard has it all jumbled, and I just kind of went across it as I was typing...)

Spoiler:
For the sake of my solution, I'll label the daemons A, B, and C.

#1) Ask A: Do you always tell the truth?
#2) Ask B: Do you always tell the truth?


At this point the line of questions diverge. If both answers are the same, we know that "yes" is what they answered. In this case, skip to #3 (and remember that we now know what "yes" and "no" are). If they differ, we know A or B is the random daemon, and then we need to ask the following:

#2a) Ask C: Do you always tell the truth?

This now assures that 2 of our responses to this question are the same. Again, "yes" is that duplicated response. This leads us to the last question in this line:

#2b) Ask C: Does [whichever daemon answered "yes" out of A and B] always tell the truth?

This is basically the classic form from Labrynth, and we know to invert whichever answer we get. At this point we know which one is always random, and from this last question which of the others always tells the truth. Obviously then, the last daemon always lies and we've won!

#3) Ask B: Does C always tell the truth?

If "no", skip to #4. If "yes", then the remaining possibilities are:

Truth Random Liar
Truth Liar Random
Liar Random Truth

We now know that A is not the random daemon, and we can reference their answer from question #1 to find out which of these cases we have. If it turns out A always tells the truth (otherwise we already win), then we ask:

#3a) Ask A: Does B always tell lies?

Bam! Victory

#4) Ask C: Does A always tell the truth?

If "no", we have:

Truth Random Liar
Liar Truth Random
Liar Random Truth

To solve, (since A either always lies or always tells the truth) jump back to question #3a.

If "yes" we are reduced to:

Liar Truth Random
Random Truth Liar

And since B must always tell the truth...

#5) Ask B: Does C always tell lies?

I think that finishes it.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 5 guests