# How does a common man solve impossibly hard truthteller/falsifier questions?

How does one solve the World's hardest puzzle, and other questions of the type? Is there a proper approach to such a question, or does one just have to be incredibly smart to do so?

And here's an even harder version, where you can illustrate the method used.

There are 4 gods. 3 of them are Truth, Random and False. Truth always speaks the truth. False always lies. Random will give a random answer, either true or false. The 4th god has a behaviour exactly the same as one of the 1st 3. He is a clone of Truth, Random or False, but you don't know which. None of the 4 can be identified, except through their responses.

How many yes-no questions must you ask, to figure out which character is found in 2 gods (which type of god has been cloned)?

If you're up for some more....

The gods answer ja or da, in their own language, and you don't know which means yes, and which means no. All gods use the same language. How many questions are required to identify the repeated trait?

• Fun fact to the last part: "ja" is german for "yes", and "da" is russian for "yes". – Gully May 21 '15 at 13:28

I'll assume you don't just want the solutions to these puzzles which has already been answered on this site in the case of "The Hardest Logic Puzzle Ever", and you are looking for some more general advice for these sorts of puzzles.

The usual trick to solving these problems is to craft your questions in a way that gets the same information back regardless of who is asked.

For example if you want to know the answer to some question X you could ask:

What would that guy say if asked X?

If you ask this question to a truth teller while pointing at a liar, you will get the liars answer. If you ask this to a liar while pointing at a truth teller you will also get the liars answer.

If you just asked X you would get back two different answers and be none the wiser. By asking about how another guy would answer you can get a consistent answer that can be reversed to know the truth.

Another common trick is to ask questions to provide more than one piece of information such as for your even harder problem:

If I asked both of you X would you both give the same answer?

If asked to a liar about himself and the truth teller he will answer with the lie, yes.

With this single question you have discovered the identities of two people with only one question. Of course if there were only two people to start with this isn't really any better that finding out about one of them and then inferring about the other. Note that this particular question doesn't work so well with a random answerer involved. Have a think about how this question would play out with different combinations of respondents.

The random answerer can be a bit problematic. If you ask a truth teller how will that guy answer when pointing at Mr Random what is he supposed to say? Does he have prior knowledge of all future random choices? If it is not explicitly stated in the puzzle how these situations are supposed to work in can make your problem even more difficult.

You probably don't have to be incredibly smart to solve these types of puzzles, but being reasonably smart and knowing these sorts of question strategies really helps.

Here's the secret:

None of these puzzles are difficult. In each puzzle, there are only finitely many possible scenarios (in the most famous two guards and two doors puzzle, there are only four possible scenarios, and in the gods puzzle you describe there are only 72 possible scenarios). Questions you can ask can be classified by which scenarios result in a "yes" answer, which scenarios result in a "no" answer, and which scenarios result in a random answer (or "da"/"ja"/random). That means that the number of functionally different questions you can ask is at most three raised to the power of the number of scenarios (and in practice it is a lot smaller, since you can take advantage of various symmetries of the problem). Now just check each type of question in order, and see which one works. If you get to ask several questions, then the number of possible strategies increases, but again a brute force approach will eventually get you to a solution.

For instance, here is the complete idiot's method of solving the standard two guards/two doors puzzle (one lies, one tells the truth, one door to freedom, the other to death, one question):

In questions where there are no random answers and we are looking for one piece of information with one question, there is a slightly cleverer method:

Say there are N possible scenarios, numbered 1, ..., N, and we want to know if statement X is true. In each scenario, write f(i) for the answer you would receive in response to the question "Is X true?" in scenario i, and write g(i) for whether X is actually true in scenario i. Suppose, for example, that N is 4, f(1) is "da", f(2) is "ja", f(3) is "ja", f(4) is "da", g(1) is true, g(2) is true, g(3) is true, and g(4) is false. Let's say we want to come up with a question where if we hear the answer "ja" it will mean that X is true. Then we make the question: "Is it true that we are either in scenario 2 or in scenario 3 or in scenario 4?", where we include exactly scenarios i where either f(i) is "ja" and g(i) is true, or f(i) is "da" and g(i) is false.

When there are random answers, it is a bit trickier.