Reply
Wed 4 Oct, 2006 09:57 pm
George Boolos, a brilliant MIT logician has called this puzzle, the greatest logic puzzle of all time. Before you even try to answer this problem, I will warn you that the answer is NOT simple and NOT easy to come up with. Don't waste too much time on this problem. Here it goes:
Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for "yes" and "no" are "da" and "ja," in some order. You do not know which word means which.
Some answers to questions that people will have:
It could be that some god gets asked more than one question (and hence that some god is not asked any question at all).
What the second question is, and to which god it is put, may depend on the answer to the first question. (And of course similarly for the third question.)
Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.
Random will answer da or ja when asked any yes-no question.
Good luck, and remember no cheating (i.e. using google).
Quote:I look forward to the correct answer, assuming there is one.
I have it, but I just want to torture you and everyone else a little more before I post it.
If it weren't for not knowing yes from no, I'd have a solution. Ask A if B lies more often than C. Based on the reply, you can determine which of B and C is non-random. From there, it's pretty straightforward.
but what if A is the random one?
Then it doesn't matter which of B or C you choose.
Ask A if B is more likely to lie than C.
If A says yes, B is non-random.
If A says no, C is non-random.
Code:A B C A's response Non-random
----------------------------------
T L R Y B
T R L N C
L T R Y B
L R T N C
R T L Y/N B/C
R L T Y/N B/C
Gravenewworld wrote, "
I just want to torture you and everyone else a little more
"
With that sort of attitude, you will fit right in.
Just don't go posting riddles about trips to St Ives!
I'll post the answer in 1 week. Until then, keep trying
.
C'mon only a few more days until the answer is up. Anymore stabs at the answer?
If Try and markr can't get it, I'm not going to even take a stab.
Can you hold off a few more days? I'd like to keep working on this right now, but it's 1:00 a.m., and I have to get to bed.
With the first question, I can identify a non-random person.
With the second question I can determine the meaning of ja/da.
If I can't figure out a third question that will provide the rest of the information, then I think I need to figure out a second question that will tell me if the non-random person I identified is the liar or the truth-teller and go from there.
Sure no problem. Should I post any hints?
I don't want any hints other than am I on the right track with only determining the non-random person with the first question? In other words, should I have determined more information than that with the first question?
Quote:Sure no problem. Should I post any hints?
Please, if you will, there is no need for you to post an answer at all. Just let us think about it. If we cant solve it we wont deserve to know the answer, or we can look for it by cheating elsewhere.
markr wrote:If it weren't for not knowing yes from no, I'd have a solution. Ask A if B lies more often than C. Based on the reply, you can determine which of B and C is non-random. From there, it's pretty straightforward.
Maybe if we somehow combine what we have we can get it.
In 2 questions I can determine the word for yes/no and the partial identity of one God (only partial because I cant account for Random).
Q1 = Ask(A, "Are you all named True?")
Q2 = Ask(A, "Is your name True?")
If (Q1 == Q2)
{
A is named False or Random
Q1 is word for "yes" (word for "no" can be assumed known)
} else
{
Q1 is word for "no"
Q2 is word for "yes"
A is named True or Random
}
Quote:I don't want any hints other than am I on the right track with only determining the non-random person with the first question? In other words, should I have determined more information than that with the first question?
You are on the right track, but yes you should determine more info from the first question. Your logic is too simplistic.
Quote:Maybe if we somehow combine what we have we can get it.
Yes!! This is the type of thinking that is needed to solve this problem. In logic, how do you combine ideas into one statement so that if the statement is true then BOTH ideas must be true or if the statement is false then both ides must be false?
"if the statement is true then both ideas must be true"
This is done with the AND operator.
"if the statement is false then both ideas must be false"
This is done with the OR operator.
However, you can't do both at the same time because TF and FT have to map to T or F.
My first question posed to A is:
Would the liar say "ja" if asked if the truth-teller would say that B is more truthful than C?
A "ja" response implies B is non-random.
A "da" response implies C is non-random.
It's easy to determine the meanings of ja and da with the second question posed to the non-random person previously identified:
Are you the truth-teller?
The response means yes.
Unfortunately, this appears to leave too much to determine with the third question. So, either the first or second needs to be beefed up to obtain more information.
markr,
You have used 2 questions and all you have determined is the meaning of ja/da.
This can be determined with one question:
"Are you lying now?"
The response will always mean "no"
This will always work but takes 4 questions.
Code:
Q1 = Ask(A, "Are you not random?")
Q2 = Ask(A, "Do you all have the same name?")
If (Q1 == Q2){
A is named random
Q3 = Ask(B, "Do you all have the same name?")
Q4 = Ask(B, "Is your name True?")
if (Q3==Q4){
Q3 is word for "yes"
B is named False
C is named True
} else {
Q3 is word for "no"
B is named True
C is named False
}
} else {
A is True or False
Q3 = Ask(A, "Is your name True?")
If (Q3 == Q2){
A is named False
Q3 is word for "yes"
Q4 = Ask(A, "Is B random?")
if (Q4 = "no"){
B is named Random
C is named True
} else {
B is named True
C is named Random
}
} else {
A is named True
Q3 is word for "no"
Q4 = Ask(A, "Is B random?")
if (Q4 = "yes"){
B is named Random
C is named False
} else {
B is named False
C is named Random
}
}
}
nevermind, there's a mistake in the Q1 != Q2 path.
Quote:However, you can't do both at the same time because TF and FT have to map to T or F.
Sure you can. That is the logic behind "if and only if" statements (which you sometimes see written as "iff" or <===>). In mathematics when you do a proof for theorems that contain if and only if statements, you assume the first idea to be true and prove the 2nd. Then you assume the 2nd is true and then prove the first one.
Quote:However, you can't do both at the same time because TF and FT have to map to T or F.
Sure you can. That is the logic behind "if and only if" statements (which you sometimes see written as "iff" or <===>). In mathematics when you do a proof for theorems that contain if and only if statements, you assume the first idea to be true and prove the 2nd. Then you assume the 2nd is true and then prove the first one. when both are proven true, then the statement as a whole is true.
Stumble It!
Tweet This
Bookmark on Delicious
Share on Facebook
Share on MySpace