a logic problem for a friday morn

Jessica Sant
Sheriff
Posts: 4313
http://philosophy.hku.hk/think/logic/hardest.php

They claim its the hardest logic problem out there. I certainly don't know the answer... any ideas?

Paul Bourdeaux
Ranch Hand
Posts: 783
Wow. Only three questions really makes it tough... I will look more this weekend when I have time to waste.

marc weber
Sheriff
Posts: 11343
Your task is to determine the identities of A, B, and C by asking three yes-no questions...

As any programmer/developer recognizes, the first thing to do is change the business requirements. My initial proposal is to adopt a phased approach under which we implement a dual-god model that effectively eliminates the Random variable. Not only will users find this a much more stable and predictable platform, but it's sure to mitigate future troubleshooting expenditures. Next, in response to feedback from business partners (see above), we need to upgrade the i/o module to accommodate more than 3 questions. Because this is a Goal-Driven Initiative (GDI), I'm recommending a 64-question buffer to help ensure deliverable realization.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
This is an interesting one. What I'm wondering is, how much knowledge do these gods have? Specifically - do True and False know what Random will say to any given question? If they don't, then it's possible to ask questions which cannot be answered. In this case, I've found a solution in which it's possible to determine the identities of all three gods using only two questions. I suspect this is not the intended solution though, so I guess I'll have to assume the omniscience of the gods supersedes Random's ability to be truly random. No free will in this universe, I guess - not even for gods. Will have to think some more, later...

Paul Bourdeaux
Ranch Hand
Posts: 783
He He He... I was stuck on one central part, and I had to resort to googling to figure it out (I was soooo close, yet so far...).

Here is a hint. You must use the iff (if and only if) operator. I was stuck because I kept using the boolen AND operator . In case your boolean logic is rusty, the rules for iff are:

A iff B = (A && B) || (!A && !B)

A iff B iff C = A iff D where D = B iff C

FYI, in response to our earlier question about whether or not True and Fals eknow what Random will answer, it turns out that they dont. Asking an unanswerable question does work to identify the Random god, but you still don't know if da or ja mean yes... There is a three question solution without asking any unanswerable questions.
[ December 30, 2005: Message edited by: Paul Bourdeaux ]

Marc Peabody
pie sneak
Sheriff
Posts: 4727
After busting my noodle for a while I did find that you must use some kind of and/or conditions to the questions, as Paul hinted.

I also discovered a question that can identify who is the random god (half the time) without creating an "unanswerable" question:
-----------------------------------
Is exactly one of the following true?:
1) You always tell the truth
2) da means yes
-----------------------------------
The answer to this will always be ja unless the random guy happens to answer da. If the first god was the one to say da, you can figure it all out by asking the second, "Does da mean yes?" (truth will always say da and false will always say ja) and then asking the final one, "Do you tell the truth?" to find out which of da/ja means 'yes'.

So I have a 1 in 6 shot of ensuring victory.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Ah, googling is for wimps.

I came up with a way to ask any god anything, and know whether the answer means true or false. From there, it's easy. This technique does require that any given statement from any god (including Random) be either true or false, never indeterminate. Of course in the real world such an assumption would be erroneous, but it seems to be a valid assumption for this puzzle, from the way it's phrased. Furthermore without this assumption I'm pretty sure there is no way to guarantee a solution with only three questions.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
[Paul B]: Here is a hint. You must use the iff (if and only if) operator.

Actually no, I don't have to.

My question uses one if, one and, no ors.

FYI, in response to our earlier question about whether or not True and False know what Random will answer, it turns out that they dont.

My solution works whether they know or not. You can simply avoid any question they might possibly not know the answer to.

Interestingly, in my solution I never actually learn whether da means yes or no. Don't really need that info. There's no possible way to get that info and identify all three gods in only three questions, unless you allow unanswerable questions (and know in advance that True and False cannot predict Random's behavior.) If you know that, you only need two questions to identify all three gods anyway, so again, there's no reason to care whether da means yes or no.

Marc Peabody
pie sneak
Sheriff
Posts: 4727
Originally posted by Jim Yingst:

My solution works whether they know or not. You can simply avoid any question they might possibly not know the answer to.

... If you know that, you only need two questions to identify all three gods anyway, so again, there's no reason to care whether da means yes or no.

I agree that the question doesn't state that you need to figure out which of da/ja means yes/no. But I'm skeptical, Jim. I'm skeptical. How in the world could you identify them all with only asking a question to two gods? The random dude is a pain in the rear!

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Well, you've just got to know how to talk to gods, you see.

I would hint that feedback is key - involving the truth or falshood of a statement within the question itself. That way two falsehoods can be converted to a truth. But your previous posts indicate you're going down that track anyway - good. So I'll add that you can introduce an additional constraint on a god's behavior as a hypothetical clause in the question, such that it is impossible to answer the question either truly or falsely without being affected by the constraint.

Ram Bhakt
Ranch Hand
Posts: 145
Long long time ago I encountered (and succussfully solved) a kiddie version of this problem. It goes as follows:
There are two guys. One always speaks the truth and the other always lies. You can ask only one question, to any of the guys, and find out identify the liar (and the honest guy).

My answer was simple: Pick any guy (say, A) and ask him this: If I ask the other guy (B) that are you (i.e A) a liar, what will he say? If he (A) responds No, he is a liar.

I was trying to build up on the same mechanism for this tougher version and I am stuck. In fact, I don't think it can be solved in just three question. The reason is the random guy. The thing is that since the question has to be directed to someone (i.e exactly one person) , there is a chance that you picked the random god and in this case, the result of the question will not give you any usable information. (Basically, having a Random gate at the end of the circuit will totally destroy the information contained in the message. So Random gate has to be joined with a deterministic gate to preserve the information).

One question that I formulated is as follows:

If I repeatedly ask the other two gods whether ja means yes, will they BOTH (at the same time), EVER, say ja?

Let the Gods be named as H (honest), L (Liar), and R (Random). There are five possibilities:

Case 1:

question posed to H: His answer will always be da, irrespective of whether ja means yes or no.
question posed to R: He answers da

Case 2:

question posed to L: His answer will always be ja, irrespective of whether ja means yes or no.
question posed to R: H3 answers ja

Case 3:
question posed to H: da.
question posed to R: ja

Case 4:
question posed to L: ja.
question posed to R: da

Case 5:
question posed to H: da.
question posed to L: ja.

Now, only in case 1 and case 2 (i.e. in cases where both the responses are same) can you find the solution with the one remaining question, and that too only if the meaning of ja and da are known.

In the other 3 cases, you cannot. SO the point is that there is one more variable to solve for than the number are equations that we can to formulate using 3 questions. So either we need to fix the random guy or need to know what da/ja means.
The same issue exists with the kiddie version as well. If you don't know Yes or No, you can't find out using just one question.

Would like to hear your thoughts.

BTW, I am assuming we cannot ask questions that depend on information base, such as "Is it a Day?".

Ram Bhakt
Ranch Hand
Posts: 145
Originally posted by Ram Bhakt:

The same issue exists with the kiddie version as well. If you don't know Yes or No, you can't find out using just one question.

I take that back. Question would be (to A): "If I ask the other guy (B) that do you (A) respond as ja for a question whose answer is yes, the what will he (B) say?"
If he (A) aswers ja, he is a liar.

But if one of the guys is random (instead of being the opposite of another), it cannot be solved by one question.
[ January 03, 2006: Message edited by: Ram Bhakt ]

Jim Yingst
Wanderer
Sheriff
Posts: 18671
It may help to consider a slightly simpler version of the problem in which they gods simply answer yes or no, which mean exactly what we'd expect. If you can solve this version (which is not easy, but I still assert it is possible) then the solution to the da/ja version can be arrived at with only minor modification.

In fact, it may be helpful to consider an even simpler version. Imagine there's only one god, Random, who answers yes or no. There's a way to ask him any yes/no question you want, and understand the answer. It's actually somewhat similar to Ram's answer to the "kiddie" version. With a bit of enhancement.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
[Ram]: BTW, I am assuming we cannot ask questions that depend on information base, such as "Is it a Day?".

I can't tell what this means - sorry.

Ram Bhakt
Ranch Hand
Posts: 145
Originally posted by Jim Yingst:
[Ram]: BTW, I am assuming we cannot ask questions that depend on information base, such as "Is it a Day?".

I can't tell what this means - sorry.

Something like, "Is Washington DC the capital of USA?" Does that make sense?

Ram Bhakt
Ranch Hand
Posts: 145
Originally posted by Jim Yingst:

Imagine there's only one god, Random, who answers yes or no. There's a way to ask him any yes/no question you want, and understand the answer. It's actually somewhat similar to Ram's answer to the "kiddie" version. With a bit of enhancement.

I can't think of anything (payload) that will keep its information content intact after passing through a randomizer

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Regarding "information base" - still not sure what you're saying. You can assume that, since they're gods, they probably know a lot of stuff. The solution doesn't depend on whether they know the average airspeed of an unladen swallow, for example.

Regarding losing information in a randomizer - what if you can find a way to take that random gate and apply it twice, with the same state each time? I.e. tell the truth twice, or lie twice.

I don't know if anyone else has been thinking about this - I don't want to give out the answer prematurely. But if everyone else has lost interest, then I can. Or I could e-mail you my answer I suppose.

Ram Bhakt
Ranch Hand
Posts: 145
Originally posted by Jim Yingst:
Regarding losing information in a randomizer - what if you can find a way to take that random gate and apply it twice, with the same state each time? I.e. tell the truth twice, or lie twice.

Yes, I thought about that but then realized that as long as a random gate stands independently ("in series" instead of "in parallal") in a circuit, there is no way you can get that info back. Randomizing twice will not give you anythin because feedback to the Random gate will have no effect on the output.

You know, I am getting suspicious whether you really have the answer: D

Jim Yingst
Wanderer
Sheriff
Posts: 18671
[Ram]: You know, I am getting suspicious whether you really have the answer: D

Heh. Just for that, I'm going to let you suffer a little longer. But see my earlier comment about possibly introducing an additional constraint.

Ram Bhakt
Ranch Hand
Posts: 145

Jim Yingst
Wanderer
Sheriff
Posts: 18671
All right, PM sent.

Ram Bhakt
Ranch Hand
Posts: 145
Thanks, Jim. I thought about it and I still think that that wouldn't cut it with the random guy. I don't think your question will work. May be I am missing some finer naunces of English but I think if the final response is coming out of the random guy, no matter how many loops you have before it, the response will be useless.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Well! See if I send you any more solutions.

OK, I will repeat my solution here in invisible ink:

If I were to come back tomorrow and ask you, "Are you True?", and if you were to answer that question just as truthfully as you're answering this question now, would your answer be "da"?

And more discussion:

Remember, the answer from Random isn't just a random "da" or "ja". It's a random truthful answer, or a random untruthful answer. Here is the chapter from Boolos' book in which he describes the problem. He further elaborates: "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."

Now imagine we ask Random to answer the question above. And let's say his internal coin comes up heads, and da means yes. What it his answer? What if the coin is heads and da means no? And what if the coin is tails and da means yes? Or no? Random is forced to answer ja in all four cases. If we ask the same question to True, he will answer da, whether da means yes or no. And False will answer ja. So this one question does determine whether the unknown god is True or not. We can then use the same technique to construct one or two more followup questions - that part's easy.
[ January 03, 2006: Message edited by: Jim Yingst ]

Ram Bhakt
Ranch Hand
Posts: 145
Originally posted by Jim Yingst:
Well! See if I send you any more solutions.

Sorry, I missed the joke here

Originally posted by Jim Yingst:

Remember, the answer from Random isn't just a random "da" or "ja". It's a random truthful answer, or a random untruthful answer. Here is the chapter from Boolos' book in which he describes the problem. He further elaborates: "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."

I think you (or Mr Boolos) are changing the rules of the game here. When you say random, I understand exactly as a flip of a coin. Everytime you ask a question, the guy flips a coin and answers yes or no.

If I understand you correctly now, what you mean is that whether the God is a liar or honest is unknown at the time the question is asked, (instead of random). So for a given question, the guy either becomes honest or a liar but not random. This brings a determinitic-ness to his behaviour and that removes the "hardest ever" part of the puzzle. It pretty much boils down to the kiddie puzzle.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
[Ram]: Sorry, I missed the joke here

I was pretending to be offended because you disagreed with me. "See if I send you..." is an implied threat, like saying "next time, you will see that I won't send you a solution!". Of course I'm joking, and I'm not offended.

I think you (or Mr Boolos) are changing the rules of the game here.

I don't believe so, no. Bringing in the Boolos quote may seem unfair since it wasn't available as part of the puzzle, but I believe it really says the same thing the original problem statement did. It just says it more clearly. The original text said "whether Random speaks truly or falsely is a completely random matter". This implies that he must either speak truly, or speak falsely, but which one he chooses will be random. Which is what I've been saying in several posts, starting with December 30, 2005 03:26 PM. The original text ("speaks truly or falsely") is a little vague - that's why clarified what I thought it meant, in my 03:26 post.

When you say random, I understand exactly as a flip of a coin. Everytime you ask a question, the guy flips a coin and answers yes or no.

He does flip a coin, and he does answer yes or no (da or ja), but the problem never said that da and ja must be random. It said that speaking truly and speaking falsely are random.

If I understand you correctly now, what you mean is that whether the God is a liar or honest is unknown at the time the question is asked,

Well, he can also lie on one question and speak truly for a different question. We can't say he is a liar, or honest, because that's not a permanent state.

No, the decision to lie or tell truth is still random. It's determined by a coin toss, each time a question is asked.

So for a given question, the guy either becomes honest or a liar but not random.

OK, since he just used a coin to determine whether to be honest or lie, I have no idea what you mean by "not random".

This brings a determinitic-ness to his behaviour

His behavior is partly deterministic - with the right question it's very deterministic. But he still gets to randomly choose whether to tell a truth or a lie. He just ends up with the same result either way.

and that removes the "hardest ever" part of the puzzle.

Well I thought "hardest ever" was a silly thing for an MIT logic professor to say. It isn't the hardest puzzle ever. But this is the puzzle the way Boolos himself intended it, as show by the quote from Boolos' book.

It pretty much boils down to the kiddie puzzle.

Once you solve the problem of how to deal with the random guy, and how to deal with the fact you don't know what da and ja mean.
[ January 03, 2006: Message edited by: Jim Yingst ]

Ram Bhakt
Ranch Hand
Posts: 145
Thanks a lot for your detailed reply, Jim. I understand it now.
I feel that it is probably not the hardest puzzle. Even harder would be the case that I was imagining, where the random god answers truely randomly. It can be solved in 5 questions. Would like to hear if somebody can solve it in less than 5.

The reason I did not call the current situation as random is because this God (gate) respects the "feedback", which is the property that you are utilizing to convert it to a True gate (irrespective of whether it is a Open gate or Not gate). While a true random gate will ignore the feedback, thus wasting your question.

marc weber
Sheriff
Posts: 11343
Despite knowing better, I ran this by my girlfriend, who majored in philosophy, and got 15 minutes of questions along the lines of...
• Why are these entities considered "gods," and who labeled them as such?
• How is "god" defined in this context?
• Why are certain gods providing false or random answers?
• Who is telling us that the gods behave in this way, and how do they know?
• Where did this question come from?
• Why do we need to know the answer?
• Etc...
• :roll:

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Marc: I was going to say "you should know better" but I see you've acknowledged that. So I have nothing to add.

Ram, for your version of the question:

If all the gods are guaranteed to answer da or ja, as originally stated: 4 questions.

If True and False do not know what Random will do, and if they are permitted to answer na (no answer) to any question they do not know the answer to:

If Random is also permitted to answer na: 3 questions

If Random cannot answer na, only da or ja: 2 questions

Have fun.