Jump to content
Sign in to follow this  
SDG

the hardest logic puzzle ever

Recommended Posts

From Wikipedia:

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.

Additional problem statement clarifications at Wikipedia, but be careful not to accidentally see discussion of the solution(s).

I worked on this on and off yesterday and finalized my solution this morning. In addition to a concrete solution, I also abstracted some of the logic underlying all possible solutions as discussed at Wikipedia. (Some of the extended discussion around

Random's behavior and "exploding god-heads"

seems needlessly fussy to me.)

A friend who is a math genius solved it after about a half-hour of serious thinking with pencil and paper (plus some preliminary thinking earlier in the day). After thinking the problem over for a few minutes, he gave me a clue that probably helped me to solve it a lot faster than I would have otherwise.

If you want the clue, here it is:

It matters that we know in advance the words for yes and no (da and ja), even though we don't know which is which, since we can put the words into our questions.

Share this post


Link to post
Share on other sites

I would think a problem with this puzzle is that the assumption that Random would answer differently each time. But what if Random answers as "Da" would, consistently, each of the three times, out of complete randomness? Does the solution bear this in mind?

Share this post


Link to post
Share on other sites
I would think a problem with this puzzle is that the assumption that Random would answer differently each time. But what if Random answers as "Da" would, consistently, each of the three times, out of complete randomness? Does the solution bear this in mind?

Random's behavior is like flipping a coin; past performance is no guarantee of future results. You could get three heads in a row, three tails, or any any possible permutation thereof.

The solution methodology does take this into account.

Note: One version of the solution depends on hair-splitting whether Random randomly chooses to answer "Ja" or "Da" versus whether he randomly chooses to be truthful or false. However, it is possible to propose a solution that works regardless which of these is the case, or even without addressing the question at all.

Edited by SDG

Share this post


Link to post
Share on other sites

Some clarifications from Wikipedia:

  • 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.
FWIW, I'm pleased to say that my solution is a variant significantly different from any listed at Wikipedia, though it follows the same essential strategy that all possible solutions must follow.

Share this post


Link to post
Share on other sites

SDG, do all the gods speak the same language? If I establish that A says "ja" for yes, may I then presume that "ja" from B or C also means yes?

Share this post


Link to post
Share on other sites

Does True, False and Random know each other? That is, if I

ask one about another, will they be able to answer it--to the fullness of who they are

?

Share this post


Link to post
Share on other sites
SDG, do all the gods speak the same language? If I establish that A says "ja" for yes, may I then presume that "ja" from B or C also means yes?

Yes. "Ja" always has the same meaning for all three (whether it is "Yes" or "No"). So any question for which Truth would answer "Ja," False would always answer "Da," while Random might give either answer.

Does True, False and Random know each other? That is, if I

ask one about another, will they be able to answer it--to the fullness of who they are

?

Very, very key question. The answer is YES -- all three know which is Truth, which is False and which is Random. That really should be in the official clarifications.

Share this post


Link to post
Share on other sites

If you get it right do you eventually get to meet David Bowie sporting an 80s Fantasy wig?

Matt

Share this post


Link to post
Share on other sites
If you get it right do you eventually get to meet David Bowie sporting an 80s Fantasy wig?

Heh. I recently reviewed that movie for the Register (new DVD) but haven't managed to get it up on the site yet. Of course the version of the "two guards" puzzle in that movie is the pushover kid brother of this puzzle.

Okay, it's time for a major hint (for those who want it; I'll spoiler it out).

I already mentioned above the hint I got from my math genius friend after he had a few minutes to think about it, viz.

It matters that we know in advance the words for yes and no (da and ja), even though we don't know which is which, since we can put the words into our questions

.

That's a significant clue, but here's an even bigger push in the right direction:

For any version of a solution to the puzzle, the goal of the FIRST question is to identify with certainty

one god who is NOT Random

.

This can be done with certainty in one question; in fact, there are a number of ways of doing it. (The method I came up with, which I like best, is not documented at the Wikipedia article, but it totally works. In fact, I like it better than the solutions at Wikipedia.)

Share this post


Link to post
Share on other sites

I had three ideas on how to solve it. My first idea took me about a half-hour to try and led to zip. My second idea took me about 15 minutes to try and led to zip. My third idea, which was to

try to force one of the three to be not random, and then ask him/her the other two questions

worked beautifully.

Dale, who knew his 800 on the analytic section of the GREs would come in handy one day

Share this post


Link to post
Share on other sites

Woo hoo! Congratulations Dale.

I am curious how, after correctly identifying the first question problem, you ultimately resolved it. As I mentioned above, Wikipedia mentions two different ways, neither of which I like as much as my (AFAIK) otherwise undocumented method.

Wikipedia's first method, from George Boolos's solution, is

a complicated logical construction such as "Does 'da' mean yes if and only if you are True if and only if B is Random?" or "Are an odd number of the following statements true: you are False, 'ja' means yes, B is Random?"

That looks like too much pencil and paper work to me, and I've never even tried to figure it out.

Wikipedia's other method is to use

a particular form of counterfactual called the "liar's paradox," according to which if you ask a liar, "If I were to ask you X, what would you answer?" the liar will lie about the lie that he

would have told you, and in a binary-answer question you will get the truth

. This approach seems a bit cheesy to me, and so my method, which is more intuitive than the first approach, does not rely on the

liar's paradox

, though it does use

counter-factuals

.

Here is my version of the first question, addressed to A:

"If I were to put a question to B and C, such that B answers 'Da' and C answers 'Ja,' is the answer to the question No?" Whichever answer A gives will be the same as that ascribed in my counter-factual to a remaining god who is not Random. Thus, if A says 'Da,' B is not Random, and if A says 'Ja,' C is not Random.

The principle, of course, is that

for any question that elicits

differing answers from Random and either of the other two gods, the remaining god will always agree with Random over against the other. Thus, if B and C are Random and False, then Random's answer is true and True will agree with Random, and if B and C are Random and True, then Random's answer is false and False will agree with Random

.

It might be a bit easier and more intuitive to phrase the question

"If I were to put a question to B and C, such that B answers 'Da' and C answers 'Ja,'

is the answer 'Da' or 'Ja'?" Then whichever god whose answer A did not repeat would be not Random.

But this might be felt to be not a true yes-no question, hence the method above.

Share this post


Link to post
Share on other sites

I used the

"liar's paradox"

, although I didn't know it by that name.

Dale

Share this post


Link to post
Share on other sites
Here is my version of the first question, addressed to A:

"If I were to put a question to B and C, such that B answers 'Da' and C answers 'Ja,' is the answer to the question No?" Whichever answer A gives will be the same as that ascribed in my counter-factual to a remaining god who is not Random. Thus, if A says 'Da,' B is not Random, and if A says 'Ja,' C is not Random.

The principle, of course, is that

for any question that elicits

differing answers from Random and either of the other two gods, the remaining god will always agree with Random over against the other. Thus, if B and C are Random and False, then Random's answer is true and True will agree with Random, and if B and C are Random and True, then Random's answer is false and False will agree with Random

.

It might be a bit easier and more intuitive to phrase the question

"If I were to put a question to B and C, such that B answers 'Da' and C answers 'Ja,'

is the answer 'Da' or 'Ja'?" Then whichever god whose answer A did not repeat would be not Random.

But this might be felt to be not a true yes-no question, hence the method above.

wow. nice work SDG. I started writing about 3 different posts stating what I thought were (minor) problems with your method, but then after thinking about them as I typed, found your reasoning is sound. The only minor thing I think needs to be tightened up--and I might still be off here...my head hurts--is a stipulation about

your hypothetical question that is couched within your first question to god A.

Asking "is the answer no?" could be an irrational question, and may be impossible to answer if the hypothetical question to gods B and C were a question that might have more than one appropriate answer. That is, if you employ the liar's paradox (If I asked...would you answer...), asking "is the answer no?" becomes irrational since there could be more than one answer, since it is subjective. For example, if god A is True; god B, False; and c, Random, and saying that the hypothetical couched question was, "what would you say if I asked you if the sky was blue?," True (god A), (let us assume he knows the question that was hypothetically asked) would know that god B (False) would say 'yes' and Random must have randomly said no this time, but it is impossible for True to know whether Random was telling the truth or not because, if he is truly random, not even he knows what he WOULD answer IF asked. So to speak of THE answer being no, yes or anything definite is untenable. Maybe I'm being too nit-picky. I just wonder if there are any other kinds of questions that might, if they're not expressly excluded, disable your strategy.

I still think your logic is sound. You may just have to work in a little modification to close that loophole. Or maybe I'm totally off base; it is late.

Let me know if I've gone screwy...

Share this post


Link to post
Share on other sites
wow. nice work SDG. I started writing about 3 different posts stating what I thought were (minor) problems with your method, but then after thinking about them as I typed, found your reasoning is sound.

Thanks, yank eh! Funnily enough, right after I posted my solution here, I sat down to explain my solution to a coworker -- and wound up getting confused and unsure if I was right after all. I didn't mind my coworker thinking I was nuts, but the thought of Dale ripping into my supposed solution here and showing me for a fraud was more than I could bear. ::blushing:: So I left my coworker, went back to my cube, sat down and worked it all out again, breathed a sigh of relief, went back and explained it the right way to my coworker, and went back to work.

Concerning your one misgiving: I think that

the unequivocal answers "Da" and "Ja" hypothetically elicited from B and C imply a question with one correct answer

. However, if we wanted to eliminate any possible misgivings on this point, we could always tweak the Question 1 scenario to something like

"If I were to put to B and C a factual yes-no question admitting only one possible correct answer..."

. I guess that would do it?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×