Freethought & Rationalism Archive

excreationist · 03-22-2002, 08:15 PM

Kachana:
I came up with a similar problem that appears to be impossible... could you tell me if my problem is actually solvable?

In this problem, there are two people, A and B. One understands English and answers your questions correctly, the other doesn't understand English and mentally flips a coin. You have to ask them a limited number of questions which have definite yes or no answers to tell which person is which.

Let's say you asked both of them these questions:
1) Do you understand English?
2) Do both of you understand English?
3) Does the other person understand English?
4) Are your answers random?

And in 1 out of 16 times, both people would answer
1) yes
2) no
3) no
4) no

So in that set of questions, there is a 1 in 16 chance that both people will give identical answers and so be indistinguishable.

There would also be a chance that the random person would give the same answers to the person who answered falsely.

So is there a set of questions that *always* can distinguish between those two people? (one of which doesn't understand English)

If there isn't a 100% reliable solution to this it seems that your question would also not have a 100% reliable solution.

Bill Snedden · 03-22-2002, 08:53 PM

Quote:

Originally posted by excreationist:
I came up with a similar problem that appears to be impossible... could you tell me if my problem is actually solvable?

If the solution of which I'm thinking is the correct one, then it should be applicable to your problem as well. I'll think about it some more tomorrow...

Bill

PS. Malaclypse - I think the answer is yes, but I'm not sure. I'm going to see if I can put my answer in an algorithmic format.

excreationist · 03-22-2002, 09:38 PM

Quote:

Originally posted by Bill Snedden:
If the solution of which I'm thinking is the correct one, then it should be applicable to your problem as well. I'll think about it some more tomorrow...

To make my problem even simpler, there could be just one person, and you've got to determine whether they can understanding English yes-no questions or not in a limited amount of time.
So do you (or anyone else) think that there is a limited set of questions that could *definitely* determine whether that person is answering randomly or can actually understand English?
Let's say you can ask them up to 4 questions with definite yes-no answers.

Kachana · 03-23-2002, 04:43 AM

*****may contain spoliers to a possible solution to the original question******

excreationist,

given your problem, here's one thing you could do.

Ask A: If I asked you if B understood English, would you say yes?

If A = Not-English the answer will be yes or no at random.
If A = English, then B = Not-English, so the answer will be no.

So, if the answer is 'yes', we know that A is random.

If the answer is no, then we could continue until a 'yes' was given, or give the same question to B and wait for a 'yes' to be given, which will tell us that B is random.

Some may see this as cheating (keeping on asking a question to see if someone is answering at random), but I think it would work, unless I've made a stupid mistake somewhere.

Bill_C · 03-23-2002, 05:32 AM

Kachana,

[edited to add]
I posted my response before I read your hint, and it is uses the idea you presented, my response seems redundant now. But it looks like I am on the right track.
[edit]

I think that I figured out the answer. Let me know if I made a mistake. First of all I would like to rule out possible approaches to the problem. First of all, the are 3!=6 possible arrangement. (This corresponds to 2.58… bits). Therefore, more than 2 questions are required to determine the identity of the Gods. (One yes or no question yields 1 bit of information.) If one wants to know the mean of da or ja, this expands the problem space to 12 possibilities (~3.58 bits) and there are not enough questions to get all this information.

Don't read futher if you don't want to know my solution.
.
.
.
.
.
.
.
.
.
.
.
.
.
The trick is to formulate questions such that if X is true (where X is a yes or no question), then the answer is da regardless of the meaning of da and ja or the truthfulness of the speaker. My formulation is as follows: If you want to know the truth of X ask "If I were to have asked X now would you have said da? Thus you can get the truth of X by embedding it in the former question. The God will respond da if X is true and ja if Y is false regardless of the God asked or the meaning of ja or da. (It took a bit of time to verify this, and I can explain further if anyone wants – hopefully I didn’t make a mistake)

Now it is fairly simple to ask 3 questions the yield the identity, and there is more than one way to do it. Here is one solution.

Three questions (read X) to be asked any God in order
1. Are the identities of Gods A, B, C (in order) TRF or TFR or RTF?
2. Are the identities of Gods A, B, C TRF or RFT?
3. Are the identities of Gods A, B, C TFR or FTR?

The responses to the questions are given below.

ABC response
TRF da, da, ja
TFR da, ja, da
RTF da, ja, ja
RFT ja, da, ja
FTR ja, ja, da
FRT ja, ja, ja

These question yield unique answers for each unique arrangement, so the identities can be determined.

Bill

[ March 23, 2002: Message edited by: Bill_C ]

[ March 23, 2002: Message edited by: Bill_C ]

John Page · 03-23-2002, 06:23 AM

Quote:

Originally posted by Bill_C:
These question yield unique answers for each unique arrangement, so the identities can be determined.

Ya beat me to it (although I haven't worked through your solution yet)! However, I did get sidetracked thinking about the following issue, which I was just about to ask for guidance on.

Can you assume that the gods know the truth about the other gods?

If you can not assume so, I think the problem unsolvable - for similar reasons Kant used to deny pure rationalism.

If, on the other hand, you assume the gods do know the truth about each other, you are implying some knowledge about gods that cannot be substantiated. (Ergo, gods are only hypothetical because we don't actually know whether they know the truth.)

This goes back to my original query about gods (for there are none), and if one substitutes dogs, the problem is likely unsolvable for the same reason - we don't know whether dogs know the truth.....

Do you agree?

Cheers!

Kachana · 03-23-2002, 09:46 AM

Bill_C
.
.
.
.
.
.
.
.
.
.
.
The idea you have of using a nested question of the form "If I asked X would you say 'da'" so that information can be gained irrespective of the meaning of the individual words is spot on, and is used in the solution in the paper!

The questions you gave are not the same as in the paper, and are certainly more complex. Maybe I'm missing something, but I don't see how Random won't mess things up in your solution

For instance, if ABC = TRF, you give the three responses as : Da, da, ja, irrespective of which God is asked which question.

Now I see that if True is asked the first question, he will say da if the Gods are in any of those orders.

I can also see that if False was asked the first question he would similarly reply Da, given that he would lie about his answer to the unembedded question.

But what about Random, he might say either da or ja to question 1, which could cause confusion with the order: RFT

Hope I'm not completely missing the boat here??

[edited as one of my da's was next to a colon and turned into a smiley!]

[ March 23, 2002: Message edited by: Kachana ]

Bill Snedden · 03-23-2002, 09:55 AM

Quote:

Originally posted by Bill_C:
The God will respond da if X is true and ja if Y is false regardless of the God asked or the meaning of ja or da.

But if you've happened to choose the "random" god to ask the question, how can you depend upon the answer being da for true and ja for false?

It is certainly true that the solution lies in "nesting" the truth value of a question within the question (hint, hint!), but it seems to me that it will take at least two questions to determine whether or not any one of two gods is true or false and then a third question to confirm the identities of all three.

Bill

PS. Oops! Cross-post with Kachana!

[ March 23, 2002: Message edited by: Bill Snedden ]

Bill_C · 03-23-2002, 12:46 PM

Kachana,

Thanks for the great problem. I woke up around 4:00 am and thought I had solved the problem but I was wrong. I went back to sleep and when I woke up again is when I came up with what I have now.

Let me explain how the it doesn’t matter if I pick the random God. Perhaps I am misunderstanding though. My understanding is that Random can choose to either lie to the current question posed, or tell the truth to the particular question posed. The question was designed based upon the idea that the truth value picked (for the embedded) was the same (or refers to) the truth of the actual question posed. Suppose he decides to give the truth on question Q1 and lie on question Q2. Further suppose the X1 and X2 are both true for the sake of illustration.

Q1: If I were to ask you X1 now (meaning for this question instead of my current question) would you say da?

If Random choose to tell the truth for Q1: He would have in fact said da (if da is true otherwise ja) if X1 were in fact asked. To tell the truth to the actual question he would say da or (if da means no he would still say da since he actually would have said ja to X1).

Q2: If I were to ask you X2 now (meaning for this question instead of my current question) would you say da?

If Random choose to lie for Q2 he would have in fact said ja (da) if X2 were asked. To lie the direct question he would say da (da if da means no)

So for Random, it doesn’t matter if he lies or not as long as the question is phrased properly. That is, the question has to refer to how he is responding to the current question. I have tried to do that. He will either behave exactly like the True or False for each individual question and it doesn’t matter which.

As for the breakdown of the questions X, I could have stated it more simply like "Ask A if either A or B were Random" etc. You can get to the same result but typically you get an asymmetric breakdown. This can lead having to ask different questions based upon the responses given. The formulation was my way of being lazy. I wanted to be able to write the fewest number of questions with the least explanation. My solution is a dumb way to ensure that the first question divides the solution space exactly in half. I would not be surprised if there are better ways to do this.

Thanks,

Bill

[ March 23, 2002: Message edited by: Bill_C ]

jpbrooks · 03-23-2002, 02:56 PM

I'm viewing this thread rather late, but this is quite interesting! I'm not certain what discipline (mathematics [game theory] or logic) deals directly with puzzles of this type.

03-23-2002, 05:32 AM	#15
Bill_C Junior Member Join Date: Dec 2000 Location: Cedar Rapids, IA Posts: 5	Kachana, [edited to add] I posted my response before I read your hint, and it is uses the idea you presented, my response seems redundant now. But it looks like I am on the right track. [edit] I think that I figured out the answer. Let me know if I made a mistake. First of all I would like to rule out possible approaches to the problem. First of all, the are 3!=6 possible arrangement. (This corresponds to 2.58… bits). Therefore, more than 2 questions are required to determine the identity of the Gods. (One yes or no question yields 1 bit of information.) If one wants to know the mean of da or ja, this expands the problem space to 12 possibilities (~3.58 bits) and there are not enough questions to get all this information. Don't read futher if you don't want to know my solution. . . . . . . . . . . . . . The trick is to formulate questions such that if X is true (where X is a yes or no question), then the answer is da regardless of the meaning of da and ja or the truthfulness of the speaker. My formulation is as follows: If you want to know the truth of X ask "If I were to have asked X now would you have said da? Thus you can get the truth of X by embedding it in the former question. The God will respond da if X is true and ja if Y is false regardless of the God asked or the meaning of ja or da. (It took a bit of time to verify this, and I can explain further if anyone wants – hopefully I didn’t make a mistake) Now it is fairly simple to ask 3 questions the yield the identity, and there is more than one way to do it. Here is one solution. Three questions (read X) to be asked any God in order 1. Are the identities of Gods A, B, C (in order) TRF or TFR or RTF? 2. Are the identities of Gods A, B, C TRF or RFT? 3. Are the identities of Gods A, B, C TFR or FTR? The responses to the questions are given below. ABC response TRF da, da, ja TFR da, ja, da RTF da, ja, ja RFT ja, da, ja FTR ja, ja, da FRT ja, ja, ja These question yield unique answers for each unique arrangement, so the identities can be determined. Bill [ March 23, 2002: Message edited by: Bill_C ] [ March 23, 2002: Message edited by: Bill_C ]</p>

03-23-2002, 09:46 AM	#17
Kachana Regular Member Join Date: Oct 2000 Location: Bristol, UK Posts: 279	Bill_C . . . . . . . . . . . The idea you have of using a nested question of the form "If I asked X would you say 'da'" so that information can be gained irrespective of the meaning of the individual words is spot on, and is used in the solution in the paper! The questions you gave are not the same as in the paper, and are certainly more complex. Maybe I'm missing something, but I don't see how Random won't mess things up in your solution For instance, if ABC = TRF, you give the three responses as : Da, da, ja, irrespective of which God is asked which question. Now I see that if True is asked the first question, he will say da if the Gods are in any of those orders. I can also see that if False was asked the first question he would similarly reply Da, given that he would lie about his answer to the unembedded question. But what about Random, he might say either da or ja to question 1, which could cause confusion with the order: RFT Hope I'm not completely missing the boat here?? [edited as one of my da's was next to a colon and turned into a smiley!] [ March 23, 2002: Message edited by: Kachana ]</p>

03-23-2002, 12:46 PM	#19
Bill_C Junior Member Join Date: Dec 2000 Location: Cedar Rapids, IA Posts: 5	Kachana, Thanks for the great problem. I woke up around 4:00 am and thought I had solved the problem but I was wrong. I went back to sleep and when I woke up again is when I came up with what I have now. Let me explain how the it doesn’t matter if I pick the random God. Perhaps I am misunderstanding though. My understanding is that Random can choose to either lie to the current question posed, or tell the truth to the particular question posed. The question was designed based upon the idea that the truth value picked (for the embedded) was the same (or refers to) the truth of the actual question posed. Suppose he decides to give the truth on question Q1 and lie on question Q2. Further suppose the X1 and X2 are both true for the sake of illustration. Q1: If I were to ask you X1 now (meaning for this question instead of my current question) would you say da? If Random choose to tell the truth for Q1: He would have in fact said da (if da is true otherwise ja) if X1 were in fact asked. To tell the truth to the actual question he would say da or (if da means no he would still say da since he actually would have said ja to X1). Q2: If I were to ask you X2 now (meaning for this question instead of my current question) would you say da? If Random choose to lie for Q2 he would have in fact said ja (da) if X2 were asked. To lie the direct question he would say da (da if da means no) So for Random, it doesn’t matter if he lies or not as long as the question is phrased properly. That is, the question has to refer to how he is responding to the current question. I have tried to do that. He will either behave exactly like the True or False for each individual question and it doesn’t matter which. As for the breakdown of the questions X, I could have stated it more simply like "Ask A if either A or B were Random" etc. You can get to the same result but typically you get an asymmetric breakdown. This can lead having to ask different questions based upon the responses given. The formulation was my way of being lazy. I wanted to be able to write the fewest number of questions with the least explanation. My solution is a dumb way to ensure that the first question divides the solution space exactly in half. I would not be surprised if there are better ways to do this. Thanks, Bill [ March 23, 2002: Message edited by: Bill_C ]</p>

Thread Tools	Search this Thread
Show Printable Version	Search this Thread: Advanced Search

03-22-2002, 08:15 PM	#11
excreationist Veteran Member Join Date: Aug 2000 Location: Australia Posts: 4,886	Kachana: I came up with a similar problem that appears to be impossible... could you tell me if my problem is actually solvable? In this problem, there are two people, A and B. One understands English and answers your questions correctly, the other doesn't understand English and mentally flips a coin. You have to ask them a limited number of questions which have definite yes or no answers to tell which person is which. Let's say you asked both of them these questions: 1) Do you understand English? 2) Do both of you understand English? 3) Does the other person understand English? 4) Are your answers random? And in 1 out of 16 times, both people would answer 1) yes 2) no 3) no 4) no So in that set of questions, there is a 1 in 16 chance that both people will give identical answers and so be indistinguishable. There would also be a chance that the random person would give the same answers to the person who answered falsely. So is there a set of questions that always can distinguish between those two people? (one of which doesn't understand English) If there isn't a 100% reliable solution to this it seems that your question would also not have a 100% reliable solution.

03-23-2002, 04:43 AM	#14
Kachana Regular Member Join Date: Oct 2000 Location: Bristol, UK Posts: 279	***may contain spoliers to a possible solution to the original question**** excreationist, given your problem, here's one thing you could do. Ask A: If I asked you if B understood English, would you say yes? If A = Not-English the answer will be yes or no at random. If A = English, then B = Not-English, so the answer will be no. So, if the answer is 'yes', we know that A is random. If the answer is no, then we could continue until a 'yes' was given, or give the same question to B and wait for a 'yes' to be given, which will tell us that B is random. Some may see this as cheating (keeping on asking a question to see if someone is answering at random), but I think it would work, unless I've made a stupid mistake somewhere.

03-23-2002, 02:56 PM	#20
jpbrooks Senior Member Join Date: Aug 2000 Location: Chicago Posts: 774	I'm viewing this thread rather late, but this is quite interesting! I'm not certain what discipline (mathematics [game theory] or logic) deals directly with puzzles of this type.

Freethought & Rationalism Archive

The archives are read only.