Hardest Puzzles #1: Logic Puzzles
If you’re finding yourself getting stuck on the Army Of Zero puzzles, here’s a bit of light relief, in the guise of a series of blog posts about the hardest, most fiendish puzzles in the world! After these, you’re going to be glad to come back to Army Of Zero…
This week I’m going to point you towards the hardest logic puzzle ever, according to philosopher George Boolos. I’ll add more posts at future dates about other kinds of puzzles.
OK, here we go, hold on tight to something. This is what is reputed to be the hardest logic puzzle:
Three gods A, B, and C are called, in some order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are ‘da’ and ‘ja’, in some order. You do not know which word means which.
So it’s similar to what’s known as the knight/knave puzzle, in which you’re asked to imagine yourself on an island where some of the population always lie and the rest always tell the truth, you don’t know which is which, and you have to find a reliable way of getting the truth out of someone. Only in this version, it’s way, way harder because (a) you might be talking to someone who lies or tells the truth at random, and (b) you don’t know whether their answer means “yes” or “no”.
My brain is melting out of my ears. If you want to read more - and see the solution - go and have a look on Wikipedia.
January 2nd, 2010 at 4:58 am
*SPOILER ALERT, KINDA*
Spoilers in that I’ll be mentioning a solution to the simpler knight/knave puzzle, and I suspect that it will be a component of the solution to the crazy ‘three gods’ puzzle.
Anyway…I came across this puzzle as a kid, in a rather awesome book linked to The Crystal Maze. I’ve always known the solution to the simpler knight/knave puzzle because it’s solved in the movie Labyrinth (where the protagonist has to solve it to choose between two possible doors, but even the correct door turns out to have a trap behind it because the labyrinth is just completely unfair, hehe).
Sarah’s approach to the knight/knave puzzle in Labyrinth was something to the effect of “what would the other guy say if I asked him?”. A more direct approach is “what would you tell me if asked you?”. I’ve never quite been sure how the random dude is supposed to respond to such questions. Wikipedia has cleared up one of my queries: “if you ask him the latter question, how does he answer” - I always assumed he’d actually listen to the question, in which case he himself runs up against his own capricious nature, but Wikipedia explains that in fact he’s so shallow that he doesn’t actually pay any attention to the question at all, so he won’t have any problem blurting out an answer. But…
If you take Sarah’s approach, and ask God A (who happens to be one of the others) “what would that god there say if I asked him such-and-such?”, while pointing at the ignore-the-question-and-answer-at-random god, what does God A then do? He doesn’t actually know what answer I’d get if I asked Mr. Random, but he can’t really summarise that complication with his limited speaking vocabulary - I guess the closest he could manage would be his word for ‘no’.
I’ve taken care not to read the solution on Wikipedia, but I did glance at the section on exploding heads, hoping to find a resolution to the above. I’m reluctant to read it too closely, as apparently it’s linked to the solution, but a cautious glance suggests it doesn’t address the issue I’ve described.
Ten seconds of thinking has suggested an approach which would work adequately if only the gods answered in English, but alas, I’m gonna have to spend rather longer pondering how to handle the version where they speak in Godlish.
January 2nd, 2010 at 5:55 am
Argh, looking more closely at the problem description on Wikipedia, perhaps I completely misunderstood what it said about Random. I originally parsed it as “he essentially flips a coin and answers yes for heads and no for tails”, but a more accurate rendition would be “he essentially flips a coin and answer truly for heads and falsely for tails”. So…if you ask him a reflexive question (”what would you say if I asked you X?”), how does he work out his answer? I can see four possibilities:
1) He flips his coin first and then answers the question as if he *always* got that result on a coin flip.
OR
2) He flips his coin once for the hypothetical situation described in the question and then again when determining whether to report his conclusion honestly (thus effectively making the first part of his thought process irrelevant).
OR
3) He wants to explain that he doesn’t know what he might say if you were to pose such a question, since he doesn’t yet know which way the coin would land when he was answering the hypothetical question. Of course, as I described in my earlier comment, he doesn’t have the vocabulary available to explain that hitch, and is essentially tongue-tied, much like the other two gods would be if we asked them a question about how Random would answer some question.
OR
4) The description on Wikipedia is poorly phrased and my original interpretation was correct. This seems unlikely, as if it were the case, surely they’d have used the less ambiguous phrasing that I used above.
I think (1) is the most likely possibility. If it’s true, then still I think the Wikipedia description could be somewhat better phrased, so…
Either these considerations are completely irrelevant to the actual solution, so no-one one Wikipedia thought to make it crystal clear, OR, these considerations are key to the solution, and describing them too pedantically would be too leading.
If the latter were the case, I’d like to think I’d have solved it by now, given how much attention I’m paying to the issue.
I guess it’s part of the nature of the “hardest logic puzzle ever” that I’m getting confused about whether I’m actually confused.
January 5th, 2010 at 6:24 pm
I suppose that (1) and (2) are in effect the same thing (at least from the point of view of the person asking the question). With a bit of work, you could probably tweak your question to Random (”what would you say if I asked you X?”) so that it overcomes the apparent failing in the the way the problem is written.
I think it’s actually quite unsatisfying that the solution (at least the one given in the Wikipedia article) isn’t more elegant. It feels almost like a brute force attack. If anyone can figure out a more elegant solution, I’d love to hear it (and I’d suggest that they update the Wikipedia article accordingly and get the full credit!)