What is the most difficult logic problem you have ever encountered ? Be kind enough to mention the solution too.

Statement of the problem

It is stated as follows:
Three gods A, B, and C are called, in no particular  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.
Boolos provides the following clarifications:

>  * It could be that some god gets asked more than one question (and hence that some god is not asked any question at all).
 * What the second question is, and to which god it is put, may depend  on the answer to the first question. (And of course similarly for the  third question.)
 * 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.

Answer by Ben Baert:

The hardest logic problem that I know of is rightly called "The Hardest Logic Problem Ever" by George Boolos.

Statement of the problem

It is stated as follows:
Three gods A, B, and C are called, in no particular  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.
Boolos provides the following clarifications:

  • It could be that some god gets asked more than one question (and hence that some god is not asked any question at all).
  • What the second question is, and to which god it is put, may depend  on the answer to the first question. (And of course similarly for the  third question.)
  • 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.

Solution

Boolos provided his solution in the same article in which he  introduced the puzzle. Boolos states that the "first move is to find a  god that you can be certain is not Random, and hence is either True or  False".[1] There are many different questions that will achieve this result. One  strategy is to use complicated logical connectives in your questions  (either biconditionals or some equivalent construction).
Boolos' question was to ask A:
Does da mean yes iff you are False iff B is Random?
Equivalently:
Are an odd number of the following statements true: you are False, da means yes, B is Random?
It was observed by Roberts (2001) and independently by Rabern and  Rabern (2008) that the puzzle's solution can be simplified by using  certain counterfactuals. The key to this solution is that, for any yes/no question Q, asking either True or False the question
If I asked you Q, would you say ja?
results in the answer ja if the truthful answer to Q is yes, and the answer da if the truthful answer to Q is no (Rabern and Rabern (2008) call this result the embedded question  lemma). The reason it works can be seen by looking at the eight possible  cases.

  • Assume that ja means yes and da means no.
  1. True is asked and responds with ja. Since he is telling the truth, the truthful answer to Q is ja, which means yes.
  2. True is asked and responds with da. Since he is telling the truth, the truthful answer to Q is da, which means no.
  3. False is asked and responds with ja. Since he is lying, it follows that if you asked him Q, he would instead answer da. He would be lying, so the truthful answer to Q is ja, which means yes.
  4. False is asked and responds with da. Since he is lying, it follows that if you asked him Q, he would in fact answer ja. He would be lying, so the truthful answer to Q is da, which means no.
  • Assume ja means no and da means yes.
  1. True is asked and responds with ja. Since he is telling the truth, the truthful answer to Q is da, which means yes.
  2. True is asked and responds with da. Since he is telling the truth, the truthful answer to Q is ja, which means no.
  3. False is asked and responds with ja. Since he is lying, it follows that if you asked him Q, he would in fact answer ja. He would be lying, so the truthful answer to Q is da, which means yes.
  4. False is asked and responds with da. Since he is lying, it follows that if you asked him Q, he would instead answer da. He would be lying, so the truthful answer to Q is ja, which means no.

Regardless of whether the asked god is lying or not and regardless of which word means yes and which no, you can determine if the truthful answer to Q is yes or no. If, however, the god is answering randomly, the answer to the Question is still without meaning.

The solution below constructs its three questions using the lemma described above.

  1. Ask god B, "If I asked you 'Is A Random?', would you say ja?". If B answers ja,  either B is Random (and is answering randomly), or B is not Random and  the answer indicates that A is indeed Random. Either way, C is not  Random. If B answers da, either B is Random (and is answering  randomly), or B is not Random and the answer indicates that A is not  Random. Either way, you know the identity of a god who is not Random.
  2. Go to the god who was identified as not being Random by the previous question (either A or C), and ask him: "If I asked you 'Are you False?', would you say ja?". Since he is not Random, an answer of da indicates that he is True and an answer of ja indicates that he is False.
  3. Ask the same god the question: "If I asked you 'Is B Random?', would you say ja?". If the answer is ja, B is Random; if the answer is da, the god you have not yet spoken to is Random. The remaining god can be identified by elimination.

Source: Wikipedia

I've met quite a few people who study or have studied philosophical logic at graduate level who were baffled by this kind of problem (if they had not heard of it before, that is; most of them have), so I think while it's always hard to classify something as "the hardest problem ever", it is certainly a good candidate for this position. ­čÖé

What is the most difficult logic problem you have ever encountered ? Be kind enough to mention the solution too.

Advertisements

Leave a comment

Filed under Life

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s