Hardest Logic Puzzle Ever.

This newsletter is a follow-up to last weeks, when I presented the “second hardest logic puzzle ever.” That was a simplified version of this one. I encourage my readers to tackle that puzzle first. That said, I present the so-called “Hardest logic puzzle ever.”

Question

The following wording is from Wikipedia entry on the Hardest Logic Puzzle Ever.

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.

I will add to that you can’t ask paradoxical questions or ask the true or false god how the random god would respond to a question. All questions must have a clear yes or no answer.

What should be your line of questioning, which you may adapt according to previous responses?

Hints

With six ways to arrange the three gods and two possible words for yes, there are 12 possibilities. You would think that with only three yes/no questions you can’t narrow it down to just one possibility as 12/8 is greater than 1. That is true. However, you aren’t asked for the translation for Ja and Da. You must find an set of questions that leads to which god is which without needing to know the translations for yes and no.

It’s important to realize that it does no good to ask the random god a question. Thus, you want to waste no more than the first question being addressed to the random god.

You want to carefully frame the first question so that after the response you can narrow down one of the other two gods as either being true or false. If you asked the random god the first question, then at least you’ll know the other two gods are either true or false.

However, finding such a first question is easier said than done. My final hint is you have to involve more than one god in the question.

Answer

Label the gods A, B and C.

The following shows my three questions and who they are addressed to according to the previous responses.

Question 1

Ask A, “Consider the following three statements:

1. A is true.
2. B is random.
3. Ja is the word for yes.

 

Are the number of true statements an odd number?”

The following two tables show how this question will be answered according to the 12 possibilities of which god is which and what is the word for “yes.”

If Ja is “yes”

A	True	True	False	False	Random	Random
B	False	Random	True	Random	True	False
C	Random	False	Random	True	False	True
Yes	Ja	Ja	Ja	Ja	Ja	Ja
#True	2	3	1	2	1	1
Answer	Da	Ja	Da	Ja	Ja or Da	Ja or Da

 

If Da is “yes”

A	True	True	False	False	Random	Random
B	False	Random	True	Random	True	False
C	Random	False	Random	True	False	True
Yes	Da	Da	Da	Da	Da	Da
#True	1	2	0	1	0	0
Answer	Da	Ja	Da	Ja	Ja or Da	Ja or Da

 

Note that if we get a “Ja” answer, then C must be either the true or false god. Likewise, if we get a “no” answer then B must be either the true or false god. We wish to not waste any more questions on the random god.

Question 2 – After “Ja” Answer.

If the answer to question 1 was “Ja”, then ask C, “Is ‘ja’ the word for ‘yes’?”

Here is how that question would be answered in each of the eight possibilities left.

A	True	False	Random	Random	True	False	Random	Random
B	Random	Random	True	False	Random	Random	True	False
C	False	True	False	True	False	True	False	True
Yes	Ja	Ja	Ja	Ja	Da	Da	Da	Da
Answer	Da	Ja	Da	Ja	Da	Ja	Da	Ja

 

As you can see, whether we get a Ja or Da answer, we narrow down the possibilities from eight to four.

Question 2 – After “Da” Answer.

If the answer to question 1 was “Da”, then ask B, “Is ‘ja’ the word for ‘yes’?”

Here is how that question would be answered in each of the eight possibilities left.

A	True	False	Random	Random	True	False	Random	Random
B	False	True	True	False	False	True	True	False
C	Random	Random	False	True	Random	Random	False	True
Yes	Ja	Ja	Ja	Ja	Da	Da	Da	Da
Answer	Da	Ja	Ja	Da	Da	Ja	Ja	Da

 

As you can see, whether we get a Ja or Da answer, we narrow down the possibilities from eight to four.

Question 3 – After “Ja” to question 1 and “Ja” to question 2.

As a reminder, there are the four possibilities going into question 3.

A	False	Random	False	Random
B	Random	False	Random	False
C	True	True	True	True
Yes	Ja	Ja	Da	Da

 

Ask C, “Consider the following three statements:

1. A is false
2. A is false
3. “Ja” means yes.

 

Are zero or three of these statements true?”

Here is how it will be answered according to the four possibilities left.

A	False	Random	False	Random
B	Random	False	Random	False
C	True	True	True	True
Yes	Ja	Ja	Da	Da
#Correct	3	1	2	0
Answer	Ja	Da	Ja	Da

 

If you get a “Ja” response, then the answer is:

A	False
B	Random
C	True
Yes	?

 

If you get a “Da” response, then the answer is:

A	Random
B	False
C	True
Yes	?

 

Question 3 – After “Ja” to question 1 and “Da” to question 2.

As a reminder, here are the four possibilities going into question 3.

A	True	Random	True	Random
B	Random	True	Random	True
C	False	False	False	False
Yes	Ja	Ja	Da	Da

 

Ask C, “Consider the following three statements:

1. A is true
2. A is true
3. “Da” means yes.

 

Are zero or three of these statements true?”

Here is how it will be answered according to the four possibilities left.

A	True	Random	True	Random
B	Random	True	Random	True
C	False	False	False	False
Yes	Ja	Ja	Da	Da
#Correct	2	0	3	1
Answer	Ja	Da	Ja	Da

 

If you get a “Ja” response, then the answer is:

A	True
B	Random
C	False
Yes	?

 

If you get a “Da” response, then the answer is:

A	Random
B	True
C	False
Yes	?

 

Question 3 – After “Da” to question 1 and “Ja” to question 2.

As a reminder, there are the four possibilities going into question 3.

A	False	Random	False	Random
B	True	True	True	True
C	Random	False	Random	False
Yes	Ja	Ja	Da	Da

 

Ask B, “Consider the following three statements:

1. A is false
2. A is false
3. “Ja” means yes.

 

Are zero or three of these statements true?”

Here is how it will be answered according to the four possibilities left.

A	False	Random	False	Random
B	True	True	True	True
C	Random	False	Random	False
Yes	Ja	Ja	Da	Da
#Correct	3	1	2	0
Answer	Ja	Da	Ja	Da

 

If you get a “Ja” response, then the answer is:

A	False
B	True
C	Random
Yes	?

 

If you get a “Da” response, then the answer is:

A	Random
B	True
C	False
Yes	?

 

Question 3 – After “Da” to question 1 and “Da” to question 2.

As a reminder, there are the four possibilities going into question 3.

A	True	Random	True	Random
B	False	False	False	False
C	Random	True	Random	True
Yes	Ja	Ja	Da	Da

 

Ask B, “Consider the following three statements:

1. A is true
2. A is true
3. “Ja” means yes.

 

Are zero or three of these statements true?”

Here is how it will be answered according to the four possibilities left.

A	True	Random	True	Random
B	False	False	False	False
C	Random	True	Random	True
Yes	Ja	Ja	Da	Da
#Correct	3	1	2	0
Answer	Da	Ja	Da	Ja

 

If you get a “Ja” response, then the answer is:

A	Random
B	False
C	True
Yes	?

 

If you get a “Da” response, then the answer is:

A	True
B	False
C	Random
Yes	?