For GoT: Extremely Difficult Logic Puzzle

[RocketManJames]

This is a famous puzzle that I was never able to solve. I do possesss the very difficult solution... have fun GoT. You asked for a tough one, here you go.

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.

-RMJ

[jwvdcw]

is this on the right track:

<font color="white"> I'm thinking something like asking one of them what the other one would say about the 3rd ones being the false god. Or something like that </font>

[RocketManJames]

[ QUOTE ]
is this on the right track:

<font color="white"> I'm thinking something like asking one of them what the other one would say about the 3rd ones being the false god. Or something like that </font>

[/ QUOTE ]

I honestly couldn't even tell you if you are on the right track... the track to the solution is VERY long and extremely complicated. You definitely have to ask questions to certain gods that deal with the other gods... but beyond that, I am really of little help.

When it is time to post a solution, I will be posting a paper (.pdf file) that contains this problem and its solution. Just to give you an idea of the difficulty level, this paper comes from the Harvard Review of Philosophy journal with the claim that this is the most difficult logic puzzle.

Given years to tackle this problem, I do not believe I would come up with the solution.

Also, if you (or anyone else) simply cannot wait for a solution, PM me.

-RMJ

[GuyOnTilt]

This is freaking hard. I know you said that the solution is like, pages long and stuff, but I'm still going to try to figure it out. I have a 14 hour drive that I have to make on Friday by myself, so that'll be a good time and it'll keep me awake.

Please don't post the results for a while...I'm a stubborn guy and want to at least try before you tell me the solution.

GoT

[RocketManJames]

[ QUOTE ]
This is freaking hard. I know you said that the solution is like, pages long and stuff, but I'm still going to try to figure it out.

[/ QUOTE ]

Ya, well, the questions themselves are obviously not pages long. There are 3 questions, and together, they would be the solution. However, how to get to the three questions... all the thought required, etc is what takes up several pages.

Good luck with the puzzle!

-RMJ

[GuyOnTilt]

I can do it in 4 questions, so I think I'm making progress.

Okay, now I found a way to sometimes do it in 3 questions, and always do it in 4...But I think I've hit a dead end with the track I was on.

GoT

[GuyOnTilt]

Holy crap, I think I may have the solution!!! Hold on while I type it out and make sure it makes sense...

Crap. False alarm. I swear I think I'm making progress though...

GoT

[GuyOnTilt]

I'm still making good progress I think...Here's what I've come up with so far:

<font color="white">At first I couldn't think of any single question which would gain me any information. Then I came up with one: Does "da" mean "no"? The correct answer to this question, regardless of what "da" actually means, is "ja". Therefore, if the person answers "ja", they cannot be False, and if they answer "da", they cannot be True.

Also, after thinking through things and using a couple different forms of charts, I'm pretty sure that this puzzle can't be solved by process of elimination. I don't think the questions are supposed to continually narrow down the 6 different god combinations until there's only one left. Instead, I think it's the type of puzzle that requires smaller puzzles which when put together make only one possible solution.

Also, I've found another form of question that will actually give me information: IFF questions (if and only if).

Also, {I don't think I need; I don't think it's possible} to determine the meanings of the words "da" and "ja" to find the solution.

That's where I am so far.
</font>

[Chu]

Tell me if I'm on the right track, but I would think the first question would have to be "Does Ja mean Yes in english?"

[RocketManJames]

You are clearly making progress... good work!

-RMJ

[GuyOnTilt]

Okay, more progress:

<font color="white">If I can find one god that is NOT Random with my first question, I will have the solution. My final 2 questions involve the first question I came up with followed by an IFF question that uses Q2 as it's first qualifier and asks the identity of another god with the second qualifier. </font>

GoT

[GuyOnTilt]

I am so freaking close. Btw, for other trying this, using tables is the easiest way to do this for me. My mind couldn't see things as clearly without them, but tables (not grids) make this much easier on me.

GoT

[jwvdcw]

GoT, you have definitely impressed me with how well you're doing here. I know the answer, and I didn't think you'd even come close.

[jwvdcw]

If you want any hints, feel free to ask...although, it would be pretty cool to see someone get this all by themselves.

[GuyOnTilt]

If you want any hints, feel free to ask...although, it would be pretty cool to see someone get this all by themselves.

Hints are for cheaters!!! /images/graemlins/grin.gif

I'd probably take you up on the offer, but when I'm as close as I think I might be, there's no way I'm going to taint my victory!

GoT

[RocketManJames]

[ QUOTE ]
Tell me if I'm on the right track, but I would think the first question would have to be "Does Ja mean Yes in english?"

[/ QUOTE ]

No, the first question for the solution that I have is much more complex than that. This is not to say that there isn't a more elegant solution that might have that as Question #1, but the solution I have is not so simple as that.

-RMJ

[Cyrus]

My idea would be to involve all three in most, if not all, questions. (I have not looke (http://people.ucsc.edu/~jburke/three_gods.pdf)d for the solution so far but I have read GoT's posts. They're more fun than the puzzle!)

In another, similar but simpler puzzle, the one involving the 2 guards/gods, one of whom always lies and the other tells the truth, the way to go was involving them both in a question, in such a way as to negate the lie. The answer to that simpler puzzle was to ask a god/guard at random what would the other reply if asked where the prize is and then do the opposite. (So, in this puzzle, one question would be something like "Hey, God A, if God B was to ask God C 'Is *Yes* the meaning of the word *Ja*?', tell me what would God B say that God C answered?")

Good puzzle.

[Eihli]

If anyone posts the answer you better put us a big warning.

[Beerfund]

my freakin brain hurts after reading that

[aloiz]

After reading what GoT has come up with here's what I've come up with:
<font color="white">
The iff statements I think are really the key to this problem, and I think I've come up with a solution excluding the language factor.
The first thing you want to do is find a God who you are sure is either a true or false. You can then use an iff statement. Ask god 1 "you are the true god iff god 2 is the random god."

Going through all cases:
Case 1: God 1 is true god.
Answer: yes if god 2 is random and no if god 2 is false (T iff T = T and T iff F = F)
Case 2: God 1 is false god.
Answer: yes if god 2 is random and no if god 2 is true. (F iff T = F -&gt; T and F iff F = T -&gt; F)
Case 3: God 1 is random god.
Answer: yes/no
So if you receive a yes answer you know god 3 is true/false, and if you receive a no answer you know god 2 is true/false.

Once you have the god who you know to be true or false the rest is pretty simple.
Ask the true or false god something simple like "does yes mean yes?". If he anwers yes he's the true god and no he's the false god.

And ask that same god who you now know to be true or false if god 1 is the random god. And now you know the identities of all gods.

To figure it out with the language is probably very similar to this, just adding on a question to each iff statement like GoT possed that you know the answer to.
</font>

aloiz

[GuyOnTilt]

Hey aloiz,

<font color="white">For your proposition for what the first question should be:

I've worked through the same and similar IFF questions. Yours would work, except GodA will answer with Da and Ja, and you're not sure which means which. So you don't know if he's answering yes or no, which means your question as stated gives us no information. I've toyed with ways to force them to say Da or Ja by adding a 2nd IFF in the same question, but so far nothing's working. My chart system is making this puzzle a lot easier and I'm able to work through whether a question gives specific information much quicker.

IF, and that's a big if, I can come up with a way to find one specific god who I know is not random with my first question, it's game over. Because the first information gaining question that I thought of specifies whether the questionee is either NOT True or NOT False, if I know beforehand that they're not Random then I'll know their identity and be able to ask them another question concerning the identity of another God and know whether or not they're telling and truth or lying. I still won't know what Da or Ja mean, but I won't have to.

But that all means nothing unless I can figure out a way to gain the information I need to with my first question. If I can't figure out a way or this is no possible way, then it's back to the drawing board. I have come to the conclusion that the first question must be at least 3 parts, seperated by IFF's. It might be four though, since I've gone through just about all the related smaller questions that I can think of that would yield info, but so far there's no Ja or Da concensus on whether or not another god is Random or is not Random.

Btw, if this is one of those puzzles with no solution, that'd be really cruel... </font>

GoT

[RocketManJames]

[ QUOTE ]
Btw, if this is one of those puzzles with no solution, that'd be really cruel...

[/ QUOTE ]

There's a solution... I'm not that mean. I sent JWV the solution as per his request, and he could tell you that a solution exists.

You're certainly making a lot more progress than I thought you would make. When I attempted this problem, I got nowhere near as far as you've already gotten.

-RMJ

[GuyOnTilt]

You're certainly making a lot more progress than I thought you would make. When I attempted this problem, I got nowhere near as far as you've already gotten.

I kind of have an advantage. I was taught the theory behind logic and reasoning problems from Grades 3 thru 6 because my school entered a competition every year for them. Also, my Senior year Calculus instructor had us do a lot of them and taught us methods and rules to work through them.

Btw, may I ask who the author of this problem was? It'll probably help.

GoT

[RocketManJames]

[ QUOTE ]
Btw, may I ask who the author of this problem was? It'll probably help.

[/ QUOTE ]

[ QUOTE ]
Hints are for cheaters!!!

GoT


[/ QUOTE ]

[GuyOnTilt]

Oh c'mon. Telling me the author is less of me asking for an extra hint or cheating and more like me asking the country of origin for a vocab word. Answers very often depend on who's asking the question.

GoT

[RocketManJames]

Authors of the Puzzle:

Raymond Smullyan and John McCarthy

It was Smullyan's puzzle, and McCarthy increased the difficulty level.

-RMJ

[GuyOnTilt]

It was Smullyan's puzzle

That will definitely help. Thank you.

McCarthy increased the difficulty level.

Added the Da and Ja instead of Yes and No? Or added the Random God?

GoT

[RocketManJames]

[ QUOTE ]
Added the Da and Ja instead of Yes and No? Or added the Random God?

[/ QUOTE ]

Added the Da and Ja (foreign language component of the puzzle).

-RMJ

[aloiz]

Think I got it:
<font color="white">
Question 1: does da mean no iff are you true iff god 2 is random god

Case 1: god 1 is true god
--Case 1a: ja = yes
----Answer: ja if god 2 is random da if god 2 is not
--Case 1b: da = yes
----Answer: ja if god 2 is random da if god 2 is not

This case is somewhat confusing and what originally tripped me up. When you have three statements seperated by two iff, like A iff B iff C they are evaluated as (A iff B) iff C. So in case 1b we would get (F iff T) iff T if god 2 is random, and (F iff T) iff F if god 2 is not random. The first one evalutates to F, the second one evaluates to T.

Case 2: god 1 is false god
--Case 1a: ja = yes
----Answer: (T iff F) iff T = F says T or 'ja' if god 2 is random, and 'da' if god 2 is not
--Case 1b: da = yes
----Answer: (F iff F) iff T = T says F or 'ja' if god 2 is random, and 'da' if god 2 is not

Case 3: god 1 is random
Doesn't matter what he says because both god 2 and 3 must to be T or F.

So after asking question 1 if they respond 'ja' we know god 3 is T or F and if they respond 'da' we know god 2 is T/F.

Question 2. Asking our T/F god "does da mean no iff 1 + 1 = 2"
Case 1: T/F god is the true god
--Case 1a: ja = yes
----Answer: T iff T = T = ja
--Case 1b" da = yes
----Answer: F iff T = F = ja
Case 2: T/F god is false god
--Case 2a: ja = yes
----Answer: T iff T = T -&gt; F or da
--Case 2b: da = yes
----Answer: F iff T = F -&gt; T or da
So if we get a 'ja' we know our T/F god is true and a 'da' reveals our T/F god to be false.

Question 3: Asking our now know true or false god "is da no iff god 1 is random"
Case 1: Asking true god
--Case 1a: god 1 is random god
----Answer: if 'ja' is yes we get T iff T = T or ja
if 'da' is yes we get F iff T = F or ja
--Case 1b" god 1 is not random god
----Answer if 'ja' is yes T iff F = F or da
if 'da' is yes F iff F = T or da
Case 2 Asking false god
--Case 2a: god 1 is random god
----Answer if 'ja' is yes we get T iff T = T -&gt; F or da
if 'da' is yes we get F iff T = F -&gt; T or da
--Case 2b" god 1 is not random god
----Answer if 'ja' is yes T iff F = F -&gt; T or ja
if 'da' is yes F iff F = T -&gt; F or ja

So if we are asking question three to true god and we get a 'ja' then god 1 is random, if not then god 1 must be false god. If we are asking question three to false god and we get a 'da' then god 1 is random, if not then god 1 must be true god.

Whew think that does it. Anybody find any mistakes?


</font>

aloiz

[GuyOnTilt]

Hey aloiz,

<font color="white">Your Question 1 is flawed. I thought I had already charted this question out, but I did it again just in case, and it falls apart after the 2nd combo.

Here's how I strucutre my charts:

For the question, "Does da mean no iff you are True iff GodB is Random?" it would look like this...

Meaning of Da / Are you True? / B=R? / Answer
Yes / Yes / Yes /
Yes / Yes / No /
Yes / No / Yes /
Yes / No / No /
No / Yes / Yes /
No / Yes / No /
No / No / Yes /
No / No / No /

Instead of backslashes it would be in a boxed chart form, and then you fill in the answer based on the 3 qualifiers. The first answer in this chart would be Ja. The second answer would also be Ja. So even after two possibilities you can see that if GodA answers Ja, GodB could still be either Random or not Random, therefore not giving us any usable information with this question. The way I ordered the chart above, you'd want the answers to the question to alternate between Da and Ja. </font>

GoT

[aloiz]

<font color="white">
How are the first two ja?


Meaning of Da / Are you True? / B=R? / Answer
Yes / Yes / Yes /
Yes / Yes / No /
Yes / No / Yes /
Yes / No / No /
No / Yes / Yes /
No / Yes / No /
No / No / Yes /
No / No / No /


Yes / Yes / Yes / = T iff T iff T = T in this case 'da'
Yes / Yes / No / = T iff T iff F = F in this case 'ja'

filling in the rest i get
F -&gt; T 'ja'
T -&gt; F 'da'
F 'da'
T 'ja'
T -&gt; F 'da'
F -&gt; T 'ya'
</font>

aloiz

[GuyOnTilt]

<font color="white"> You worded the question: "Does da mean no iff you are True iff GodB is Random?"

So for the first line in the chart, Da does NOT mean no, he IS true, and B IS R, so the answer will be No since you're asking True. And since Da means yes in this line, his answer should be "Ja". In the second line of the chart, again Da does NOT mean no, he IS true, and GodB is NOT R, so his answer would again be no, which for this line is "Ja".

When there are 3 parts of an IFF question, the answer to ALL 3 parts have to be either yes or no for for answer to the question to be yes. If it's 2 and 1 or 1 and 2, the answer is no.

If you had worded the question, "Does da mean yes iff you are True iff GodB is Random?" then the first two lines of the chart would be opposites, HOWEVER this would break down once we got to the 6th line of the chart.

</font>

GoT

[aloiz]

<font color="white">

Opps, you're right about my question being "da means no", but it still works. You're doing the same thing that I originally did, in that you're evaluating the consecutive iff statements like a string of and's which they are not.


Meaning of Da / Are you True? / B=R? / Answer
Yes / Yes / Yes / = /F/T/T = (F iff T) iff T = F iff T = F ='ja'
Yes / Yes / No / = /F/T/F = (F iff T) iff F = F iff F = T ='da'
Yes / No / Yes /
Yes / No / No /
No / Yes / Yes /
No / Yes / No /
No / No / Yes /
No / No / No /


</font>

aloiz

[GuyOnTilt]

<font color="white">I'll have to check up on how 3-part IFF questions work. It's been a couple years since I worked with/on them. The way I remember it is in question "P, iff, Q, iff, R?" all parts had to be satisfied for the answer to be yes. If I'm wrong then this logic puzzle was really never very hard to begin with. </font>

GoT

[aloiz]

<font color="white">

All parts are satisfied, but you have to evaluate each pair from left to right. I'm almost positive this is the right way. And if my solution is right, I still think this is one of the most difficult logic problems I've ever seen. If you hadn't of mentioned iff statements I would probably still be trying to use and's and or's.


</font>

aloiz

[GuyOnTilt]

<font color="white">There's a big difference between a problem being hard and a problem taking a long time. This is definitely the longest I've ever had to work on or think about a logic puzzle, but it's not the hardest if your way of IFF's is correct.

Unfortunately, I don't have my books with me so I can't check up on how 3-part IFF questions work. If how you're thinking of them is correct, and it does make sense btw, then I really don't think this logic puzzle was all that hard. It took a while, but I would've solved it pretty early into yesterday if I knew how they worked. I've gone through over a dozen charts of similar questions including the one that works doing IFF's the wrong way. /images/graemlins/frown.gif </font>

GoT

[GuyOnTilt]

First, thanks for the puzzle James. It really was a great break from studying poker, as all these logic puzzles have been.

I emailed my old HS Calc instructor asking him the rules of IFF questions, and he pasted me an exerpt from a logic/philosophy book that confirmed that I was wrong about the 3 part questions. In light of that, here is my solution to the puzzle:

Q1) To GodA: Are you True iff GodB is Random iff Da means Yes?

If he answers Da, then GodB is indeed Random and I will ask the 2nd question to GodC. If Ja, then GodB is not and I will ask the 2nd question to GodB. Now, this is assuming that GodA is either True or False. But if GodA is Random instead, then his answer will be unreliable. However, this is irrelevant because if he's Random then the God I'm going to question next definitely is not, which was the whole point of this first question anyway.

Q2) To the God I now know is NOT Random: Does Da mean no?

If Da means yes, then the correct answer is no, which is Ja. If Da means no, then the correct answer is yes, which is again Ja. So if the God answers Ja, they cannot be False, and since we already know them not to be Random, they must be True. If the God answers Da, then they cannot be True, and since they aren't Random, that leaves False.

Q3) To the same God as Q2: Does da mean no iff GodX (X being either of the other gods) is Random?

If I'm speaking to the True God, then his answer to the question will be Da when GodX is Random and Ja when GodX is not. If I'm speaking to the False God, then his answer will be Ja when GodX is Random and Ja when GodX is not.

Now I will know the identities of two of the Gods and thus be able to deduce the identity of the third.

Now on another note, I'm feeling very uneasy and disappointed about something. I thought for a bit whether I should voice it or not and decided I'm going to. I spent quite a bit of time and thought on this puzzle and was able to come to the right conclusions and deduce the required method leading to a solution. I did this all on my own without the use of the internet or a key. I did talk on the phone with a friend about the problem for a little while and worked through some seeming paradoxes with him, and I did ask for the author's name, but I never "cheated" or otherwise tainted my quest to legitimately solve this puzzle.

Having said that, I was reading through this thread again just a couple minutes ago and noticed the link that Cyrus hid in his post for the first time. Naturally, I clicked on it and was taken to a pdf file that explained the puzzle and the solution and how to achieve it. The article's solution is almost conceptually identical to mine, except for the second question which is very different. I like mine better because it is a much simpler solution to the problem you have to solve and still contains no flaws or caveats. But anyway, after reading through it and comparing it to aloiz's thoughts and solution, I can't help but think that aloiz saw this article and read it before posting his solution in this thread. First, aloiz's thought process started with the first question and then worked through to the last question. However, the purpose of the first question cannot be known until you realize what the purpose of the last 2 questions are when you're working through this logic puzzle. This puzzle is designed such that you have to work semi-backward. You simply cannot start your thought process with the first question and come to the correct solution because the first question accomplishes something that you would never think to make it accomplish unless you knew what the second and third questions were.

(Paragraph break!)Also, his wording is almost verbatim to the article's, except in question 2 where the article says to just use any true statement as your secondn qualifier. These suspicions are made stronger with the omission of the excluded middle concept, which is talked about in the article and is vital to deriving the first question, in aloiz's posts. This concept is so vital that after I realized what my first question must accomplish and talking on the phone with my friend, I even mentioned the concept to him and walked him through what it meant and how to apply it (my HS Calc teacher had taught us the concept and how and when to apply it to logic problems). You simply cannot come up with the first question without understanding this concept, which isn't a well-known concept and, as far as I know, only is used in advanced philosophical discussion and logic problems. If you haven't studied either of those, I doubt you would've ever come across this concept in black and white (although it is possible) and would definitely not take mentally for granted when working through a problem.

Anyway, I'm not here to put aloiz on trial or try to make myself sound better than him. I don't know whether or not he had read the solution before posting it here, although I strongly suspect this is the case, but I do know that if he did, I'd be a little pissed about it. Similar to the comment I made about not wanting any hints when I was so close to the solution, having someone who had already read the solution give me insight or ideas really cheapens solving problems like these and is pretty dicked.

Yes, I know that it's just a puzzle and not something to get upset about, but things like this irk me.

Again, thanks for the puzzle James! It was fun! /images/graemlins/grin.gif

GoT

[The Dude]

Oh boy, aloiz, you got him going now. Danger.

[RocketManJames]

Congratulations... both of your solutions look like they work. However, I am not an expert in this field at all. But, following them, they do seem to work just fine.

I will refrain from commenting on your observation of aloiz's solution. I don't have the level of understanding in this field to judge plagirism of this sort.

Good job! I seriously would never solve this on my own given years... unless I spent the years reading a ton about various techniques and tools of logic, then I'd probably have a fighting chance.

Glad you enjoyed it.

-RMJ

[brassnuts]

I gave up after about an hour of thought on the question because I thought it was impossible to answer. I didn't think of adding ifs and iffs, never heard of "iff" until now but I think I could have figured it out quite readily if I had thought of this approach. Too late now, 'cause I've already read the solution. Oh well, great problem.

[Cyrus]

Too late for that hint I guess.

/images/graemlins/cool.gif

[daryn]

it's a sad day in nerdville /images/graemlins/wink.gif