# a logic problem for a friday morn

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

- Jess

Blog:KnitClimbJava | Twitter: jsant | Ravelry: wingedsheep

“Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning.” - Rich Cook

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.

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." *~Joe Strummer*

sscce.org

Sheriff

*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...

"I'm not back." - Bill Harding, *Twister*

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.

Good Luck. My head hurts...

[ December 30, 2005: Message edited by: Paul Bourdeaux ]

“Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning.” - Rich Cook

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.

A good workman is known by his tools.

Sheriff

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.

"I'm not back." - Bill Harding, *Twister*

Sheriff

**[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.

"I'm not back." - Bill Harding, *Twister*

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!

A good workman is known by his tools.

Sheriff

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.

"I'm not back." - Bill Harding, *Twister*

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?".

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 ]

Sheriff

*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.

"I'm not back." - Bill Harding, *Twister*

Sheriff

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

Please tell the answer....

Sheriff

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.

"I'm not back." - Bill Harding, *Twister*

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

Sheriff

Sheriff

Sheriff

*you*any more solutions.

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

To ask something like "Are you True?" instead ask:

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 ]

"I'm not back." - Bill Harding, *Twister*

Originally posted by Jim Yingst:

Well! See if I sendyouany 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.

Sheriff

**[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.

**(instead of random).**

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 ]

"I'm not back." - Bill Harding, *Twister*

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.

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." *~Joe Strummer*

sscce.org

Sheriff

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.

"I'm not back." - Bill Harding, *Twister*

It is sorta covered in the JavaRanch Style Guide. |