Question about the Hardest Logic Puzzle Ever

[Frylock]

I'm trying to work, but my brother just walked in and reminded me about this (http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever) puzzle.

My question is this. How am I to think the truth teller would answer if I were to ask him "Suppose I ask X such-and-such question. Would X answer 'ja'"? where X is actually (unknown to me of course) the Random answerer.

Is this not a proper yes-no question, meaning I can't ask this question? Or would the answer be one translatable as "no" since if I asked X the question, it's not true that X "would" answer "ja" since X might answer otherwise?

[Captain Carrot]

No, no. the hardest logic puzzle is "14 k of g in a f p d".

Mwahahaha!

[Lemur866]

This isn't a logic puzzle. The truth teller would have to answer "I don't know". If you limit the truth-teller to only be able to answer "Yes" or "No", then there are all kinds of questions that the truth teller would be unable to answer, because like this one they don't have a yes or no answer.

[Frylock]

This isn't a logic puzzle. The truth teller would have to answer "I don't know". If you limit the truth-teller to only be able to answer "Yes" or "No", then there are all kinds of questions that the truth teller would be unable to answer, because like this one they don't have a yes or no answer.
Wait. Why isn't it a logic puzzle again?

[BrandonR]

Phew, for a second I thought this was going to be about that impossible list of US states and trying to figure out how they're related/ranked.

[Indistinguishable]

My question is this. How am I to think the truth teller would answer if I were to ask him "Suppose I ask X such-and-such question. Would X answer 'ja'"? where X is actually (unknown to me of course) the Random answerer.

Is this not a proper yes-no question, meaning I can't ask this question? Or would the answer be one translatable as "no" since if I asked X the question, it's not true that X "would" answer "ja" since X might answer otherwise?
In solving the puzzle, one does not need to resolve this ambiguity. So, you might as well construe it as not a proper yes-or-no question, taking this to mean only questions which have definite answers.

[Lemur866]

Because it isn't a logic puzzle if you asked a person obligated to tell the truth, "what have I got in my pocketses?"

The truth-teller doesn't know the answer, so his only way to tell the truth is to tell you he doesn't know. But if he can only answer yes or no, he can't tell you he doesn't know. His only possible answer is "null".

If you asked him "How far is it to Cleveland", would he answer yes or no? Same problem with asking him to predict the result of a random coin toss. He can't predict it, so he can't answer yes or no because this isn't a yes or no question.

[Frylock]

In solving the puzzle, one does not need to resolve this ambiguity. So, you might as well construe it as not a proper yes-or-no question, taking this to mean only questions which have definite answers.

Alright, thanks.

[Frylock]

Because it isn't a logic puzzle if you asked a person obligated to tell the truth, "what have I got in my pocketses?"

The truth-teller doesn't know the answer, so his only way to tell the truth is to tell you he doesn't know. But if he can only answer yes or no, he can't tell you he doesn't know. His only possible answer is "null".

If you asked him "How far is it to Cleveland", would he answer yes or no? Same problem with asking him to predict the result of a random coin toss. He can't predict it, so he can't answer yes or no because this isn't a yes or no question.

If I asked him how far it is to Cleveland, he wouldn't answer, because there is no yes or no answer.

If I ask him what the random god would say, he wouldn't answer, because there is no yes or no answer.

What's wrong with saying the latter? The thing about Cleveland doesn't make it "not a logic puzzle." Why should the thing about the random god?

It's exactly what I was asking--is this a logic puzzle where the proper answer to the question is "I don't know" and so the question is disallowed, or rather, is it a logic puzzle where the proper answer is "no" meaning the question is allowed? Either way, it's still a logic puzzle.

[Indistinguishable]

If you like, Lemur866, take the problem out of ordinary language and formalize it into a very concrete piece of mathematics, which is, of course, a logical problem:

By TruthValues, I mean (the elements of) {yes, no}.
By Words, I mean {da, ja}.
By Names, I mean {A, B, C}.
By Roles, I mean {True, False, Random}.

By Languages, I mean bijections from TruthValues to Words [there are 2! = 2 of these].
By Assignments, I mean bijections from Names to Roles [there are 3! = 6 of these].
By Propositions, I mean functions from pairs of a Language and an Assignment to TruthValues [there are 2^(2*6) = 4096 of these].

There is a function PossibleResponses(L, A, N, P) from tuples of a Language and an Assignment and a Name and a Proposition to subsets of all Words, defined as follows: if A(N) = Random, then the output is all (both) Words. If A(N) = True, then the output is the singleton {P(L, A)}. Conversely, if A(N) = False, then the output is the complement of this singleton [i.e., the singleton {Not(P(L, A))}, where Not sends "da" to "ja" and vice versa].

The task is to construct a binary tree T of maximum height 3, each of whose internal nodes is labelled with a pair of a Name and a Proposition, whose two edges out of any internal node are distinctly labelled with the two Words, and whose leaves are labelled with Languages, such that for every Language L and Assignment A, for any path from the root of this tree to some leaf, if every edge along this path has the property that its label is within PossibleResponses(L, A, N, P) for the N and P the edge's starting node is labelled with, then the label of the terminal leaf must be L.

So, yeah, it's a logic problem insofar as it's a problem in mathematics, and, more specifically, the particular sort of mathematics which might be construed to lie in the subfield known as mathematical logic. The possibility of asking non-yes/no questions and such things have nothing to do with it; they are expressly outside the realm of the setup of this problem, whatever relevance you may consider them to have to logic in general.

[Indistinguishable]

If A(N) = True, then the output is the singleton {P(L, A)}. Conversely, if A(N) = False, then the output is the complement of this singleton [i.e., the singleton {Not(P(L, A))}, where Not sends "da" to "ja" and vice versa].
Sorry, I left something crucial out here. Everywhere I wrote "P(L, A)", I should have actually written "L(P(L, A))".

The task is to construct a binary tree T of maximum height 3, each of whose internal nodes is labelled with a pair of a Name and a Proposition, whose two edges out of any internal node are distinctly labelled with the two Words, and whose leaves are labelled with Languages, such that for every Language L and Assignment A, for any path from the root of this tree to some leaf, if every edge along this path has the property that its label is within PossibleResponses(L, A, N, P) for the N and P the edge's starting node is labelled with, then the label of the terminal leaf must be L.
Sorry, I messed this up a tiny bit: the goal of the problem is to figure out the Assignment, not necessarily the Language. Thus, the leaves of the (strategy-representing) tree should be labelled with Assignments (rather than Languages), and, accordingly, in the last line, the condition is that the label of the terminal leaf must be A (rather than L).

("Identification" might have been a better word than "Assignment", incidentally, but, whatever. The only point was to illustrate that this is a very concrete math problem, and thus get past any prejudice or concerns one might have over what gets to count as a genuine "logic puzzle".)

[PBear42]

Frylock, I'm a rank amateur when it comes to logic puzzles (though they fascinate me), but I think you're missing the point. AFAICT, the very reason Smullyan introduced the concept of a Random answerer was to eliminate the "What would X say ... " line of questions. Neither True or False can say. Thus, we have to solve the puzzle by other means.

[CookingWithGas]

Because it isn't a logic puzzle if you asked a person obligated to tell the truth, "what have I got in my pocketses?"

The truth-teller doesn't know the answer, so his only way to tell the truth is to tell you he doesn't know. But if he can only answer yes or no, he can't tell you he doesn't know. His only possible answer is "null".

If you asked him "How far is it to Cleveland", would he answer yes or no? Same problem with asking him to predict the result of a random coin toss. He can't predict it, so he can't answer yes or no because this isn't a yes or no question.But the puzzle explicitly states, "Your task is to determine the identities of A, B, and C by asking three yes-no questions." So by definition they can only answer yes or no.

[Half Man Half Wit]

You can still trip the whole thing up asking questions that are, in principle, answerable by yes or no, but to which any of the gods might find themselves unable to provide an answer -- as the wiki article mentions, 'Will you answer this question with 'no'?' (or: 'with the word meaning 'no' in your language'), asked of the truth teller, sends him into an irresolvable quandary: answering 'no' (or 'da' or 'ja', whichever means 'no') would be a falsehood, but so would answering 'yes'. He thus can't consistently always give a true answer and always answer 'yes' or 'no'.

[Indistinguishable]

Aye, hence my further constraint that the questions one asks should have answers decidable directly from "How do 'da' and 'ja' map to 'yes' and 'no'?" and "How do A, B, and C map to True, False, and Random?"; that is, the questions should be chosen from one of the 2^(2*6) different rows of a truth table taking such information as input.

[Chronos]

Information theory is useful in at least determining what you can and can't determine. Ultimately, you'll have three da or ja answers, which means you have 3 bits of information, enough to distinguish between 8 possibilities. There are six possible assignments of roles to gods, and 6 < 8, so you do, in principle, have enough information to figure out who's who. However, to figure out who's who and also figure out the language means you have 12 scenarios to distinguish, and 3 bits isn't enough information to do that. So you might as well just give up on trying to figure out what "da" and "ja" mean.

[Lemur866]

But the puzzle explicitly states, "Your task is to determine the identities of A, B, and C by asking three yes-no questions." So by definition they can only answer yes or no.

Yeah, see, the thing is, I missed the part where there was a link to the actual logic puzzle. I thought the OP without the link was the "puzzle". So yeah.

[Frylock]

Information theory is useful in at least determining what you can and can't determine. Ultimately, you'll have three da or ja answers, which means you have 3 bits of information, enough to distinguish between 8 possibilities. There are six possible assignments of roles to gods, and 6 < 8, so you do, in principle, have enough information to figure out who's who. However, to figure out who's who and also figure out the language means you have 12 scenarios to distinguish, and 3 bits isn't enough information to do that. So you might as well just give up on trying to figure out what "da" and "ja" mean.

Oo yikes, I think that should have been put in a spoiler box.

[Frylock]

Yeah, see, the thing is, I missed the part where there was a link to the actual logic puzzle. I thought the OP without the link was the "puzzle". So yeah.

Whoa, that must have seemed like a really bad OP.

[Indistinguishable]

Frylock has suggested spoilering Chronos's post. I don't think that's really necessary. But if mods do decide to retroactively spoiler Chronos's post, then they should spoiler the initial parts of mine which respond to it as well.
Information theory is useful in at least determining what you can and can't determine. Ultimately, you'll have three da or ja answers, which means you have 3 bits of information, enough to distinguish between 8 possibilities. There are six possible assignments of roles to gods, and 6 < 8, so you do, in principle, have enough information to figure out who's who. However, to figure out who's who and also figure out the language means you have 12 scenarios to distinguish, and 3 bits isn't enough information to do that. So you might as well just give up on trying to figure out what "da" and "ja" mean.
Although, the "da"s and "ja"s you get do not actually necessarily represent full bits of information (at least, not about just the language and role-assignments), because certain scenarios can produce either a "da" or a "ja" non-deterministically. So it's not immediately obvious that you really can determine the role-assignments mappings. [Indeed, if we modified the situation so that there was a slight chance that, say, everyone was a truth-teller, then the problem becomes impossible, even though this leaves 7 possible role-assignments, and 7 < 2^3]. But, this just pushes the maximum information you can gain down below 3 bits, so, as you said, it's clearly impossible to hope to definitely discern both role-assigments and languages.

The key to the problem is realizing that two apparent complications to interpreting responses to questions really don't matter at all:
The whole business of "How do I know whether da means yes or no?" doesn't matter at all; any proposition p you might like to inquire about can easily be turned into some new proposition p' such that p' = p if da means yes, while p' = NOT p if da means no. Specifically, take p' to be "[da means yes and p] or [da means no and NOT p]" (i.e., "(da means yes) XNOR p"). The truthful response to such a query will, of course, be 'da' if p holds, and 'ja' if p does not hold, regardless of what the language actually is.

The exact same trick also lets us forget about worrying over the distinction between Truth-teller and False-teller. Just as above, any proposition q can be turned into some q' such that q' = q if we are talking to a truth-teller, and q' = NOT q if we are talking to be a False-teller. Again, just take q' to be "(You are a truth teller) XNOR q".

So the only real complication to our getting a straight answer is the Random-responder in the mix. Using the techniques from above, the problem reduces to "There are three possible roles: Happy truth-teller, sad truth-teller, and random-responder. They will always give 'yes' or 'no' as answers; the answers are guaranteed to be correct unless you happen to ask random-responder. Figure out which of the 6 possible role-assignments is the case, using 3 questions".

I'll separately spoiler how to go from here.

Even if you'd read the above spoiler, you may wish to keep the rest spoiled:

In this reduced problem, the only obstacle to your getting a straight answer is the Random-responder. If you can, with your first question, determine somebody who is definitely not the Random-responder, then you'll have reduced the total number of role-assignment possibilities left in play down to 4, and you'll be able to just ask questions completely straight up from then on (and since you'll have two questions left, the rest is trivial; get your full bit of information each time, and you'll be done).

So it all comes down to finding a way to determine somebody who is definitely not the Random-responder with just one question. The problem has again reduced. It is now "There are three people in a line. Precisely one of them is unreliable. You get to ask the guy in the middle a 1-bit question. If he is reliable, he will give the correct bit in response; otherwise, he may give either the correct or the incorrect response bit. You win if, after your question, you can point to someone who you know is reliable."

Now, in this problem, two things strike us right off the bat: first, any formulation of a 1-bit question-and-answer protocol is as good as any other. So we might as well take our query to be of the form "Point to one of the other two guys, according to rule so-and-so."

Secondly, the guy we ask our question of (the middle guy), there's no way we could hope to end up pointing to them afterwards as definitely reliable. Because whatever answer we get from them, we could've gotten the same answer randomly if they were unreliable. So we need a question such that one response lets us be certain that the leftmost guy is reliable, and the other response lets us be certain that the rightmost guy is reliable (with this certainty holding even despite the fact that the guy doing the responding may actually be unreliable).

Thus, what it comes down to is asking the middle guy to point to one of the other two guys according to some rule, in such a way as that whoever they point to is bound to be reliable.

Well, let's just ask them "Point to someone other than yourself who's reliable (with, say, the convention of pointing to the leftmost guy if both other people are reliable)." What can we make of the results?

Well, if middleman is reliable, then we know he's done as he's been told and pointed to someone reliable. On the other hand, if middleman is unreliable, then, as he's pointed, at the very least, to someone other than himself, he's definitely pointed to someone reliable. So, in either case, he's pointed to someone reliable, just as we needed.

This solves the problem, but in case you've forgotten or gotten lost in how all these reductions work and how to put it all back together...

If you've read the above, you should have it all by now, but in case anyone just wants to see the answer by itself,

First, pick, say person A and ask them the question "Is it the case that (da means yes) XNOR (you are a truth teller) XNOR (Person B is not Random)?". [Equivalently, "Is it the case that an odd number of the following are true?: da means yes, you are a truth teller, Person B is not Random".

Given an initial response of 'da', address the following questions to Person B. Otherwise, address them to Person C.

Ask "Is it the case that (da means yes) XNOR (you are a truth teller) XNOR (you are a truth teller)?". [Equivalently, just "Does da mean yes?"]. Given a response of 'da', you know whoever you just asked is a truth-teller; otherwise, they are a false-teller.

Finally, ask "Is it the case that (da means yes) XNOR (you are a truth teller) XNOR (Person A is Random)?". Given a response of 'da', you know Person A is Random; otherwise, the one person you never asked questions of is Random.

At the end, you'll know the identities of two people, and thus of all three. Q.E.D., or something like that.

[Manduck]

This isn't a logic puzzle. The truth teller would have to answer "I don't know". If you limit the truth-teller to only be able to answer "Yes" or "No", then there are all kinds of questions that the truth teller would be unable to answer, because like this one they don't have a yes or no answer.

I don't think the truth-teller is limited to only yes or no: We are told that Random will always answer 'da' or 'ja', but we are not told that about the other two. So if we ask a yes-no question and the answer is anything other than 'da' or 'ja', we know that the god we asked is not Random, and whatever he said must be his word for 'I don't know'.

The solution to the puzzle follows so naturally that I won't insult you by explaining it ;)

[Indistinguishable]

(I hope I didn't get some minor thing backwards somewhere above, but experience guarantees I did.)

[Indistinguishable]

At some point, we're going to have to move out of spoiler tags if we hope to have any real discussion. Anyway,
[Indeed, if we modified the situation so that there was a slight chance that, say, everyone was a truth-teller, then the problem becomes impossible, even though this leaves 7 possible role-assignments, and 7 < 2^3]. But, this just pushes the maximum information you can gain down below 3 bits, so, as you said, it's clearly impossible to hope to definitely discern both role-assigments and languages.
The information-theoretic/counting* proof of this is as follows:

Suppose that, in addition to the 6 normal role-assignment possibilities, there are also K additional role-assignment possibilities (where people still respond yes/no in some fashion or another), and your task is to determine which of the 6 + K possibilities holds.

We may assume, without loss of generality, that you always address your initial question to Person A. Now, both the normal role assignments where A is Random will be compatible with either response to your initial question. As for the other 4 + K role-assignments, each will be compatible with at least one of the responses to your initial question. Thus, some response to your initial question will be compatible with the two normal role-assignments where A is Random, plus (4 + K)/2 further role-assignments; i.e., it must be possible to end your first question with 2 + (4 + K)/2 role-assignments still in play. With each further question you ask, at least one response must be compatible with at least half of these; thus, after your two remaining questions, it must be possible to end up with >= (2 + (4 + K)/2)/2^2 = 1 + K/8 possibilities still in play. If K is positive, this is > 1, meaning there must be at least 2 possibilities still in play, meaning you can't be sure which one holds. Thus, if there are any additional possible role-assignments at all, the task is impossible, even though the total number of possible role-assignments may remain <= 8.

*: for information theory is just logarithmic probability theory, and probability theory is just normalized measure theory, and measure theory is just weighted combinatorics, and combinatorics is just a fancy word for counting

[Indistinguishable]

And, incidentally, a corollary of the above tying in with a previously mentioned point,
The above counting argument also extends Chronos's observation as far as one could have imagined: it proves that no winning strategy ever allows you to ever, even by accident in some particular situations but not others, determine the language. (For if you hoped to be able to distinguish between the two languages in the case of some particular role-assignment, then you could analyze that role assignment as two correspondingly distinct possibilities in the above argument, one "normal" and one "additional").

[Chronos]

*: for information theory is just logarithmic probability theory, and probability theory is just normalized measure theory, and measure theory is just weighted combinatorics, and combinatorics is just a fancy word for countingIt's frankly amazing how useful the Pigeonhole Principle is, given how obvious it seems. But just giving it a name somehow seems to make it easier for humans to use it logically.

(the Pigeonhole Principle is basically that if you have more pigeons than pigeonholes, and put all pigeons into holes, there will be at least one hole that has multiple pigeons in it)