A Devious Puzzle (with solution)

Brian Rabern and Landon Rabern (2008) and Gabriel Uzquiano (2010) have each presented increasingly harder versions of “the hardest logic puzzle ever” (Boolos 1996), and each has provided a two-question solution to his predecessor’s puzzle. In a paper forthcoming in JPL, Pedro Barahona and I solve Uzquiano’s hardened version of the puzzle, and show why any solution strategy must include at least three questions. Finally, we introduce a puzzle of our own:

Three gods, A, B, and C are called in some order, True, Random, and Devious. True always speaks truly, and whether Random speaks truly or falsely or whether Random speaks at all is a completely random manner. Devious always speaks falsely, if he is certain he can; but if he is unable to lie with certainty, he responds like Random. 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 in their own language, in which the words for ‘yes’ and ‘no’ are ‘da’ and ‘ja’, in some order. You don’t know which word means which.

Here are the guidelines:

  1. It could be that some god gets asked more than one question.
  2. What the second question is, and to which god it is put, may depend on the answer to the first question.
  3. Whether Random answers ‘da’ or ‘ja’ or whether Random answers at all should be thought of as depending on the toss of a fair three-sided dice hidden in his brain: if the dice comes down 1, he doesn’t answer at all; if the dice comes down 2, he answers ‘da’; if 3, ‘ja’.
  4. When Devious is able to lie he does so; but if Devious cannot be sure of telling a lie, then rather than remain silent, he responds randomly like Random, i.e., there is a fair three-sided dice in Devious’ brain that is tossed when he is not certain to lie. If the dice comes down 1, he doesn’t answer at all; if the dice comes down 2, he answers ‘da’; if 3, ‘ja’.

Updated May 19th: A solution is available here.


Comments

A Devious Puzzle (with solution) — 5 Comments

  1. I don’t understand a couple of things about the puzzle

    A. Is True supposed to know the answer to questions about how Random would answer things? In other words, if I asked True the question “If I asked Random whether 2+2=4, what would he say?”, what would the answer be?

    B. Does point 2 imply that the third question *cannot* be dependent on the answer to the first two questions?

  2. (A): True will utter ‘ja’ or ‘da’ to a yes-no question he is sure to answer truthfully; if he is unsure to answer truthfully or unable to answer truthfully, True will remain silent. So, if you happened to pose your question to True, he would remain silent.

    (A*): In the original series of puzzles, False was True’s dual: each answered according to his nature just in case each was sure (or, if you prefer, able) to answer according to his nature.

    Random, in Boolos’ version and Rabern and Rabern’s, always answers. This asymmetry to True and False is a key to the 2-question solution strategies of Uzquiano, and of Rabern and Rabern.

    Uzquiano upped the ante by allowing Random the option of remaining silent, too, which breaks this useful asymmetry. Our variation keeps Uzquiano’s Random and replaces False by Devious, which breaks the dual relationship to True.

    (B): In our solution, whether you need to pose the third question depends on the particular responses to the first two questions.

    It might be that your intuitions are exactly on target but there is a sign error somewhere: for the third question depends on the answer to first two questions.

  3. There is a choice to make with respect to how True answers questions about Random’s responses.

    On the one hand True is omniscient (or at least answers all yes-no questions truthfully), so it seems he should provide the truthful answers regarding Random’s responses. This can be so even if the responses are “random”. In this case the randomization comes in by means of coin flips. So if you think that an all-knowing god could know the results of future coin flips, then there should be no problem with True answering questions about how Random would answer things. On the other hand the answers are supposed to be completely “random” and this seems to imply that they could not be known or predicted. So it really depends a lot on how we understand “random” and issues relating to the foreknowledge of chancy events. I prefer the first interpretation — Random’s answers are decide by coin flips so they are not very useful but still the gods know all the results of all the coin flips. But the second interpretation is also interesting.

    Uzquaino (2010) provides two-question solutions to Boolos’ puzzle (slightly amended) under both interpretations. If we assume True can’t answer questions about Random’s responses, then we can take advantage of the asymmetry between True and Random. But even if we assume that True can answer such questions, there remains an asymmetry between True and Random, because of “interrogative liar” questions, such as “Are you going to answer `no’ to this question?” So at least with respect to the important asymmetry issue it doesn’t really matter what interpretation we go with — although, of course, the questions will be different.

    Also note that Boolos’ second clarification included the parenthetical “(And of course similarly for the third question.)” So it seems that the answer to Weatherson’s B is “no”.

    I don’t want to give away any clues about how to solve the puzzle but I’ll just say that Devious didn’t seem to make things any more difficult.

  4. In the paper we consider the case where the gods are like us and view the coin flips (when they go off in the heads of their peers) as stochastic events, and also the case when they can predict for certain the outcome. We also consider the case where the gods refuse to name names: ask any god point blank about his or any other god’s identity, and he will remain silent. Our solution is adapted to cover all these variations.

    We had a very interesting and stimulating exchange with Landon Rabern and with referees over the issue of whether Devious made things more difficult. In the end, we thought so, but we leave it as an open question whether one could solve Devious with Rabern and Rabern’s techniques but without our bits.

Leave a Reply

Your email address will not be published. Required fields are marked *