# 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". 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.

Edit: How I would attack your puzzle:

Obviously it would take a while to do a pure brute force, so let's try being at least a little clever. First let's try the variant where everyone either tells the truth or is random, and we want to know whether there are one or two randoms. If we ask our first two questions to the two randoms, they can give any possible answers, so we need at least three questions. In fact, if we only ask three questions to two randoms and one truthteller, then the two randoms could pretend that they are truthtellers, that the real truthteller we asked is a random, and that the remaining god is a truthteller, fooling us. So we need at least four questions, and we should talk to all four people. If we ask everyone whether there are one or two randoms, then in the case of one random god we hear "one", "one", "one", and something random, in some order, while in the case of two random gods we hear "two", "two", and two random answers, in some order, and we can tell which scenario we are in regardless of how the random answers come out. So we go back to the real problem. We can make the liars act like truthtellers by asking questions like, "Is it true that either you are a truthteller and there is one random or you are a liar and there are two randoms?", so with four questions we can determine whether there are two randoms. If there is only one random, we can determine how many liars there are by taking majority opinion on a question like, "Is it true that either you are a truthteller and there is one liar or you are a liar and there are two liars?", so eight questions is enough to get by. Eight is a lot, probably we can do better. When we are polling for the number of randoms, if we hear two people confirm that there are two randoms we can stop right away, and if we hear three people confirm that there is only one random we can move on to determining who the liar is right away. If we've determined that there is only one random, we know that anyone who acted like there were two randoms is a random trying to fool us and we can ask someone else a single question to determine whether there are one or two liars (five questions used up in this case). If the lone random plays along and acts like there is only one random, then we only spend three questions determining that there is only one random, but we don't know who the random is yet, and a majority opinion from any three gods tells us whether there are one or two liars (six questions used in this case). So we can get it down to six questions, but it still feels a little wasteful. This solution is getting a little long, so I'll leave it at that for now...

• Random's answers in OP is not completely unconstrained, they are either true or false. - I could use this if I also knew that choice would be the same no matter what question I ask. May 21 '15 at 8:05
• I'm not sure you really need the spoilers. I don't think anyone is going to glance at your answer and accidentally see the solution.
– Bob
May 21 '15 at 8:18
• I always assume that Random means "they read your mind and give whatever answer will lead you to make the wrong decision, unless your strategy is foolproof, in which case they ignore your question and mentally flip a coin to give you a truly random answer." Other interpretations tend to be full of silly loopholes.
– zeb
May 21 '15 at 8:22
• @zeb That is the formulation I prefer for Random as well - It's usually what one is after and unambigous. However it does not fit with the definition given in OP. And of course one could create problems where you need to use Random for example; what if Random was defined as I do in my previous comment, and there was only one guard to the two doors? May 21 '15 at 8:26
• Then I would be forced to ask for clarification from the problem proposer: for instance how would this random respond to "Are you currently acting as if you were a liar?", or "Is your answer to this question 'no'?" As I said, silly loopholes.
– zeb
May 21 '15 at 8:31