I’m trying to work, but my brother just walked in and reminded me about this 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?
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.
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.
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.
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.
Sorry, I left something crucial out here. Everywhere I wrote “P(L, A)”, I should have actually written “L(P(L, A))”.
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”.)
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.
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.
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’.
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.
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.
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 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.
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:
[spoiler]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.[/spoiler]
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.