Friday, March 14, 2014

World’s most difficult logical puzzle explained.


Introduction.

In this article we’ll take a closer look at a puzzle created by the American philosopher and logician George Boolos, which has been described as the world’s most difficult logical puzzle. The puzzle was first published in 1996 in the Harvard Review of Philosophy and has since been republished on numerous internet sites. In addition to presenting a viable solution we’ll examine the criteria that have to be met in order to successfully solve the puzzle. We’ll also take a look at certain methods that falls just short of achieving this and demonstrate why they do so.

Some would probably argue that there are other more difficult puzzles out there and for all I know they could be absolutely right, but that is not a subject that I intend to dwell on here. I am a novice ‘logical puzzle solver’ and thus have absolutely no expertise whatsoever to offer on that particular subject. Consequently I am unqualified to pass judgment on the veracity of such a claim. People will simply have to make up their own minds regarding that particular aspect of it. I’m sure that some will probably concur and hold it to be the truth, whilst others might disagree and find the claim to be utterly false. I will however point out that the puzzle has been described in such revered terms on various websites that deals exclusively with difficult logical conundrums, and that it has been honoured with its own entry on Wikipedia corroborating that particular piece of information.

Regardless of whether it’s the most difficult logical puzzle in the world or not, it’s not unreasonable to suggest that the overwhelming majority of those who decide to accept the challenge will be likely to scratch their heads for a couple of hours before they eventually come up with the correct solution, or alternatively decide to throw in the towel in disgust. Solving it requires a substantial amount of mental effort, not to mention that some very challenging and complex scenarios will have to be thoroughly analysed before the correct answer will present itself. The puzzle contains numerous variables deliberately included to make it as challenging and difficult as possible. It should also be noted that the wording of the puzzle is rather vague, and thus leaves it open to interpretation. This is important to keep this in mind, as it is impossible to solve the puzzle without first having properly grasped the parameters by which the correct answer is to be reached. I suspect that the creator purposely planned for this, as a correct interpretation can only be obtained by employing logic and sound thinking, in other words it is part of the process that one has to go through in order to solve it.

It did take me a while to figure out the correct solution, but I managed to get there in the end and I suspect that most people who decide to give it a shot will have similar experiences. It’s definitely a fun and challenging process, not to mention almost impossible to ignore until the correct answer finally decided to make an appearance. The puzzle is reprinted in its entirety below and the solution is offered at the end of the article. Those who wish to accept the challenge should refrain, at least temporarily, from reading the text directly below the puzzle, that is of course unless they are too impatience and want to find out the correct answer straight away.

The Puzzle:

“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 also 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.

What criteria have to be present in order to solve the puzzle?

So now that we have studied the text and we’ve understood what is expected of us, how do we go about solving the darn thing? The obvious answer would be to think about the problems presented in the puzzle by using logic, and consequently come up with an acceptable and correct solution. But what if such a solution remains elusive even after several days of strenuous mental workouts? What is the best advice to give to someone who is quite literally stuck in ‘Haven’tgotaclueville’ and is unable to extricate themselves from its debilitating clutches? As in the case of any challenging mental tasks where a concise answer is difficult to conjure up, the best way to break through the seemingly impenetrable mental fog is to start eliminating that which clearly does not work. The best advice that one can offer in such circumstances is simply to wipe the slate clean and start afresh. Discard the tactics that clearly won’t get you over the finishing line and try to approach the problem from a completely different angle.

One of the most obvious questions that we have to ask ourselves if we decide to take this piece of advice onboard is to think about what types of conditions have to be present in order to solve the puzzle. We should bear in mind that a viable solution is one that will work in any configuration, i.e. that it will work regardless of which God/Gods one decides to direct the questions to. It’s not satisfactory to come up with a solution that will only work if certain specific conditions are met, i.e. that it will only work if the questions are directed to a particular God/Gods.

The first hurdle that one has to negotiate is to realize that it is essential to establish whether the God standing in front of you is truthful or untruthful after having asked the first question. This invariably means that we have to formulate the first question in such a manner that one is able to identify straight away what ‘ja’ and ‘da’ means, which will then help us to establish whether the God is telling us the truth or a fib. Admittedly this may seem like an impossible and unattainable task, but it is feasible if we go about it in a correct manner.

Another logical conclusion that we can draw is that that the puzzle in its current form cannot possibly be solved if Random decides to lie arbitrarily using our method. Solving the puzzles in just three questions hinges on the fact that Random either lies or tells the truth consistently, in other words Random has to give untruthful or truthful answers to all three questions, not just one or two, hence the earlier reference to the importance of interpreting the puzzle correctly.

The vagueness of the puzzle:

As mention previously one of the things that characterises the puzzle is its vagueness, which opens up the door to numerous different interpretations. One could of course make a strong argument of the fact that such ambiguity should be an integral part of any puzzle that tests a person’s logic abilities. It stands to reason that if a person is incapable of correctly interpreting the puzzle that he/she would also be incapable of coming up with a valid solution to the problems presented in it. There is also a very strong argument for suggesting that a person who is capable of solving the puzzle is a person that is equally capable of correctly interpreting the wording of the puzzle.

In this case a correct understanding of the puzzle would be to conclude that Random doesn’t necessarily lie arbitrarily, i.e. that he won’t necessarily lie on one question and then answer truthfully on the second and third. Based on our understanding of the text, and by running through the various scenarios that will solve the puzzle in our heads we should be able to conclude that Random could just as easily be lying consistently or he could be telling the truth consistently. This very crucial realization may not necessarily be all that obvious after a speedy perusal of the text, but it is a conclusion that one should arrive at after having studied and analysed the puzzle in more detail.

The puzzle also emphatically states that one can only ask yes-no questions. Some will probably have very rigid preconceived ideas as to what that entails. How does one define a yes-no question? The most basic way of describing such instructions would be to suggest that one is restricted to asking questions that can meaningfully only be answered with a yes or no, such as ‘Are you True?’ or ‘Is God number 2 Random?’ But couldn’t it also be interpreted to mean that one can ask the Gods questions that present very unambiguous yes-no alternative in which the Gods will have to choose between the specific yes and no alternative put forward in said particular questions? I would maintain that it does, and it is in fact my opinion that this is the way to solve the puzzle in its current form. The puzzle states that only yes-no questions can be asked, alas we can safely interpret this to mean any questions that meet those criteria should thus be accepted as valid questions.

Furthermore the puzzle doesn’t say that the person asking the questions can’t incorporate strict parameters or certain ground rules that the Gods will have to abide by when they answer those questions. The Gods may not necessarily accept these strict stipulations and they may of course choose to ignore them completely, but it doesn’t explicitly say that such criteria are off the table.

The puzzle also states that the Gods will only answer questions with yes or no, but it doesn’t say anything about whether the Gods’ ‘ja’ and ‘da’ answers (in the case of False and Random-untruthful version) has been established to unambiguously and permanently mean yes and no or no and yes, or whether in fact the answers provided by the Gods’ only mean the opposite of what the person asking the questions defines the words ‘ja’ and ‘da’ to mean in his/her questions

Methods that don’t work.

As mentioned previously any method that doesn’t instantly, and by instantly I mean after the first question has been asked, manage to correctly establish whether a God is truthful or untruthful will fail to solve the puzzle. If more than one question has to be asked in order to extract this piece of vital information then the puzzle cannot possibly be solved by asking less than four questions. The first question can be as intricate and complex as possible, but the answer it elicits will be completely irrelevant and meaningless unless we are able to establish what ‘ja’ and ‘da’ means. Without this knowledge any answer given could mean either yes or no, and the God standing in front of us could be either truthful or untruthful.

I’ll demonstrate the validity of this claim by asking a question that the Gods will have to answer differently, based on the knowledge that some of them will lie and some of them will tell the truth.

Question:

‘Are you either True, Random or False?’

This is obviously a question that True will have to answer with a yes and which False will have to answer with a no, and which Random could either answer with a yes or a no depending on his state of mind. Let’s for arguments sake say that the answer given by two of the Gods was ‘ja’. How are we then logically going to deduce what ‘ja’ means in that particular context? It could mean either yes or no, depending on the state of mind of Random.

Unless we know for sure which of the three Gods are lying and which of the Gods are telling the truth, we have absolutely zero chance of figuring out what ‘ja’ means in this particular scenario. It could mean yes, or it could mean no.

Let’s try another question;

‘If you were lying to me now, would True then give me a different answer if I asked him the same question?’

This is obviously a very sneaky question, but the result would still be the same. We would either get ‘ja’ or ‘da’ answers, which again could mean either yes or no.

The important thing to remember is as long as we have failed to establish the identity of the Gods, we‘re equally incapable of correctly deciphering what ‘ja’ and ‘da’ means.

I have decided to present an additional method that will correctly identify the Gods by asking 4 simple questions. Obviously this violates the criteria stipulated by the puzzle’s creator, but I will run through them anyway because it touches upon some of the basic ideas that are necessary in order to solve the puzzle.

In this scenario all we have to do in order to determine whether a God is ‘True’, ‘False’ or ‘Random’, is to phrase the first two question in such a way that they will have to be answered differently (yes-yes, no –yes or yes-no) depending on whether the Gods are lying or telling the truth (in this case we will only direct our questions to one God). The two questions that will achieve this task are as follows;

‘Is True always telling the truth?’ and ‘Are you telling the truth?’

In this scenario True will answer truthfully, i.e. he will answer both questions with a yes (either Ja –Ja or Da – Da). False on the other hand will answer both questions with a lie, in other words he will answer the first question with a no and the second question with a yes (either Ja-Da or Da-Ja. Random will, depending on his state of mind, either copy the answer pattern of True or False.

So why then is this an unviable approach, after all we have managed to correctly establish that the God we’ve directed our questions to is either truthful or untruthful by only asking two questions?

Well, it’s an unviable method because we have to ask two subsequent questions in order to correctly identify all three Gods. After having established that the first God is either truthful or untruthful, we then have to establish whether the God is ‘True or Random (truthful version) or whether he is in fact ‘False or Random (untruthful version). This task can only be achieved by asking two more questions.

After we have managed to establish that the first God is truthful, then the next question could be:

‘Is God number 3 False?’

To which the truthful God will answer either yes or no. If the God answers the question with a no, then we can safely conclude that God number 2 is in fact False, but we still can’t determine that God number 3 is Random (truthful version) or True. After all, the only thing that we know for sure is that God number 1 and God number 3 are truthful; we don’t know which one is in True and which one is Random (truthful version). The next question will solve this mystery once and for all.

‘Is God number 3 Random?’

Only after asking this final question can we safely reveal the identities of all three Gods, but unfortunately by adding that fourth question we will have exceeded the legal question limit set out by the creator of the puzzle.

Taking all of this information into consideration it stands to reason that it would be near impossible to solve the puzzle by only asking three questions if Random were lying or telling the truth arbitrarily, i.e. that he would answer one question truthfully and lie on the 2nd or 3rd question. In such a scenario it would be extremely difficult to establish whether the God in front of us can be trusted to tell the truth or lie without fail, which is a prerequisite for solving the puzzle. It is also worth noting that it would be very hard to tell the three different Gods apart in such a scenario. Random could simply pretend to be either False or True, and thus it would be almost impossible to tell the different Gods apart. Nor would it do us any good to ask Random about his state of mind, as we have no way of telling whether he would be lying or telling the truth, and besides even if it was somehow possible to tell it would involve having to ask an additional question which would make it unattainable to solve the puzzle in just three questions.

Thus we should be able to conclude that the answers given to us by the Gods will either have to be consistently true or consistently untrue, which means that Random will either have to lie or tell the truth consistently.

Needless to say the puzzle would be completely different if the God’s replied in English with a simple yes or no answer, but that would make the puzzle extremely easy to solve.

The solution;

Below I have drawn up the three questions that will solve the puzzle and correctly identify the three Gods. It should also be noted that all three questions are to be directed to just one God. There is no need to ask more than one God as the type of method that we employ will correctly identify the first God as either truthful or un truthful, and thus we can safely rely upon the fact that the subsequent answers given will always be either true or always untrue. Based upon this knowledge all other logical conclusions can be deduced. Please also bear in mind that I’m not claiming that this is the only way to solve the puzzle, I am merely saying that this is the method that I have chosen to employ. I do however maintain that a similar methodology will have to be relied upon in order to solve it.

Question number 1.

‘If we assume that ‘da’ means no and ‘ja’ means yes, would True then answer a question that requires a ‘ja’ in order to be answered truthfully with a ‘ja’ or ‘da’?

Question number 2.

‘If we assume that ‘da’ means no and ‘ja’ means yes, would you then answer ‘da’ or ‘ja’ if I asked you whether God number x is False/Random?’

Question number 3.

‘If we assume that ‘da’ means no and ‘ja’ means yes, would you then answer ‘da’ or ‘ja’ if I asked you whether God number x is False/Random?’

If God number 1 is True, then his first answer would be;

1         Ja 

The first answer would tell us that we’re talking with a truthful person (either True or Random – truthful version).

We then need to establish the identities of False and Random, and we do so by asking the next question. Let’s assume that the x value is replaced by God number 3 and we’re asking the first God whether God number 3 is False. Judging by the God’s next response we should then be able to safely eliminate or confirm God number 3 as False.

If the God’s answer is ‘Da’ then we can safely assume that God number 3 is not False. That would invariably mean that God number 2 is False.

Next we need to find out which one of the Gods are Random (God number 1 or God number 3). We ask the same question, but replace the x value with God number 1 and choose the Random value, i.e. we ask the first God if he’s Random (truthful version).

If the God answers ‘Da’ then God number 3 must be Random, if he answers ‘ja’ then God number 1 must be random.

Here’s the scenario with False/Random (untruthful version).

If God number 1 is False (untruthful version of Random) then his first answer would be;

2       Da

We then need to establish the identities of True and Random, and we do so by asking the next question. Let’s assume that the x value is replaced by God number 3 and we’re asking the first God whether God number 3 is True. Judging by the God’s next response we should be able to eliminate or confirm God number 3 as True.

If the God’s answer is ‘Ja’ then we can assume that God number 3 is not True. That would invariably mean that God number 2 is either True or Random. Then we’re left with a scenario where either God number 1 or 3 is False or Random (untruthful version). We need to identify at least one of them and we do so by asking the following and last question;

‘If we assume that ‘da’ means no and ‘ja’ means yes, would you then answer ‘da’ or ‘ja’ if I asked you whether God number 3 is Random?’

If the God answer is ‘ja’ then we can safely conclude that God number 3 is not Random, in which case God Number 1 must be Random (untruthful version) and God number 3 False.

So there you go, the strategy used to solve the puzzle isn’t really all that complicated, but it is highly effective in correctly establishing the various factors required to solve the darn thing. The solution also relies upon a correct interpretation of the puzzle by determining what logically makes sense and what logically doesn’t.

So go ahead and give yourself a big pat on your shoulder if you managed to come up with the correct solution. If you were unable to solve it, don’t worry too much, it is a very challenging and difficult puzzle. Maybe you will have better luck solving the next one, that is if you should decide to try to do so.


Also have a look at the alternative solution to the ‘Blue eyes riddle’.