Hacker News new | past | comments | ask | show | jobs | submit login
The Hardest Logic Puzzle Ever (wikipedia.org)
83 points by infinity on Feb 15, 2010 | hide | past | favorite | 24 comments

This reminds me of the following installment of a webcomic called "Partially Clips":


The webcomic version is easily solvable with counterfactuals (I think -- I could be wrong).

I'm pretty sure that the webcomic is flawed.

In the last panel the center head says "Yes. I was lying." A head that always tells the truth would never say this because they weren't lying before and wouldn't lie about not lying. Conversely, a lying head would lie about lying and say that they weren't lying. Thus, the center head must be the random one. However, in the first panel both the right and the left heads agree that the hero may only ask one question. Since the right and left are both either truth-telling or a liar they cannot agree with each other.

Thus, the puzzle is flawed and probably just a joke.

Given that the comic has a punch line in the bottom of the last panel, the comic is definitely a joke.

The question becomes is the author trying some subtle play or unaware of the error? (Or are you incorrect about the comic being incorrect)

Either way, it was amusing and has value.

"died of a migraine"

Sounds like the equivalent of its head exploding, albeit somewhat slower and more painfully...

I have to say, I have grown to dislike these 'logic puzzles'. I have read 'To mock a mockingbird', and examined several of these puzzles and non of them are actually hard (as in: challenging) once you realize: often you just need simple things: double negation and massive case exhaustion (and especially the latter here is just tedious and not interesting). Often, you just need the case exhaustion.

Your "case exhaustion" criticism disappears when you generalise the puzzle to more than three gods:


I really like the trick of determining the identities of 3 gods with just two yes/no questions. Simple, just ask questions that might make their heads explode. :)

Productivity denial of service attack for OCD sufferers.

is it assumed they know each other's identities or not? (you know like the gatekeeper puzzle: "what would he say if I asked him [question]...")

Yes, as I read it. All of the solutions provided depend on it.

That is a flawed puzzle. Warning, partial spoiler to the bogus solution included here.

------------- -------------

The solution proposes that for the first question, I turn to god A and ask "Hey, A, if I were to ask you 'Are you Random', would you say 'ja'?"

Either A is Random or is not - we have those two cases to consider. Let's consider the case where A is, in fact, Random - only I don't know it yet.

The problem, as stated, says that since A is Random, for each question posed to him, he "mentally flips a coin" and then answers as if he were Truth or as if he were Falsity. So while we're considering the case that A is Random, we have two sub-cases to consider: that he will answer as Truth or that he will answer as Falsity. Let us consider the sub-case where A, although Random, will answer as Truth.

Finally, we have sub-sub-cases more: perhaps 'ja' means "yes" or perhaps it means "no". And so, we'll consider the sub-sub-case where 'ja' means "yes".

So A is Random, has chosen to answer my first question as Truth, and 'ya' means yes. My question (in the bogus solution) is:

"Hey, A, if I were to ask (in your current mental state) 'Are you Random?' would you say 'yes'?"

God A (who is Random and who will answer this one question as Truth) reasons thusly. He thinks to himself:

"If this guy had asked me 'Are you Random', since I have decided to tell Truth, I would answer 'yes' ('ja').' However, that was not the question put before me - a different question was put before me.

Random (that's me, A) flips the coin once per question asked. If he were to have asked 'Are you Random' that would have entailed a coin flip separate from the current coin flip. That other coin flip could have gone either way and so, really, I might have answered 'yes' or 'no' ('ya' or 'da').

In other words, we made it clear to this guy that he was supposed to ask a simple yes or no question and instead he asked a question to which the only True answer would be 'dajadaja' [god-speak for 'maybe']."

At that point, god A would produce from his sleeve the Magic Wand of Heyting (which was manufatured during the god-wars recorded in the book of RejectingTheLawOfTheExcludedMiddle) and smite me for failing to ask a yes/no question after being clearly instructed to do so.

In other words, with the proposed (bogus) answer, should A happen to be Random, and his coin come up Truth, and should 'ja' happen to mean 'yes' -- then I will go to my grave never knowing which god is which. (Similar analysis probably applies to other sub-sub-cases.)

Very badly framed puzzle (but one that would be hard to frame soundly without giving away the intended answer).

I do believe the puzzle stated that the Random God would only flip his random coin once for the session - ie he would lie for the 1-3 questions put to him, or he would tell the truth - not flip the coin for each session.

This is in fact quite clearly described in the section Random's Behaviour about a third down the page...

I'm not sure I agree that that's what Boolo's clarification says however, it makes not a whit of difference to my analysis. For, if, indeed, "Hey A, are you Random?" is not one of my three questions, then it has no True answer other than "maybe". Conversely, if that is one of my three questions, then the bogus solution offered fails.

I believe you misunderstood the solution. You would turn to B and ask if A was random, not if he was himself random...

The problem is if B is random. The question is:

   If I were to ask you if A is random, would you say ja?
And B (who is random) processes it like this: "If he were to ask me any question whatsoever, the answer would be randomly ja or da. That means any question about that answer can't be answered, except with maybe".

That's why B is justified in smiting the asker for not asking a yes/no question.

Do you really consider it likely that such a puzzle, with such a title, which has received plenty of scrutiny from mathematicians and logicians, is flawed and such a fact would not be noted anywhere? I consider it much more likely that your analysis is flawed.

Am I the only one disappointed that this link didn't go to Fermat's Last Theorem?

Any of the Millenium Prize Problems could equally have been appropriate (with the possible exception of the poincare conjecture), but most of these require deep mathematical knowledge.

I would expect this problem to be accessible to most people with a basic grasp of logic, hence the generic title.

I generalised this puzzle to any number of gods:


doesn't require very large inferential jumps. just formulate a hypothesis that postulates a unique solution and test it.

i'd say the average code base works your brain harder.

You have only 3 questions. If you formulate a hypothesis like "A is True, B is False and C is Random", with a naive approach you will waste much more than 3 questions just to test this single hypothesis (and statistically, it will be false, so you will need to test more).

I think there's also the implied "or they will kill you" to encourage a non-brute-force method. While this one in particular doesn't mention any death threats, most problems of this kind do. I mean, why else limit yourself to their constraints, if not to preserve life / sanity / coffee / beer?

except that you aren't limited to falsifying a single premise with each question. remember guess who? the first thing you learned was to eliminate as much of the search space as possible with each step.

I believe the hardest logic test ever actually goes more like this:

There are four gods:

One always tells the truth.

One always lies.

One always chooses a random answer.

One always stabs people for trying to be clever or asking tricky questions.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact