3
$\begingroup$

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?

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

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.

If asked to a truth teller about himself and a liar he will answer truthfully no.

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.

$\endgroup$
0
$\begingroup$

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):

First we name the scenarios. Let's say FT is the scenario where the left door is freedom and left guard is truth, FL is the scenario where the left door is freedom and left guard is lying, DT means left door is death and left guard is truth, DL means left door is death and left guard is lying. Taking advantage of a symmetry, let's decide from the very beginning that we are going to ask a question to the left guard. Since questions only have yes/no answers, there are really only 16 questions we can ask. We'll classify questions by the collection of scenarios that lead to a "yes" answer from the left guard. First we have: "Are we not in any scenario at all?", which is answered with a yes in scenarios FL, DL. Second we have: "Are we in scenario FT?", which is answered with a yes in scenarios FT, FL, DL. Third we have: "Are we in scenario FL?", which is answered with a yes in scenario DL. Fourth we have: "Are we either in scenario FT or scenario FL?", which is answered with a yes in scenarios FT, DL. And so on... Our goal is to find a question which has one answer if the left door is freedom and has the opposite answer if the left door is death. Going through the list, we find that there are really only two questions that work: one is "Are we either in scenario FT or scenario DL?", which is answered with a yes in scenarios FT, FL, and the other is "Are we either in scenario FL or scenario DT?", which is answered with a yes in scenarios DT, DL. Either one of these questions solves the puzzle, and can be rephrased in other ways to make our thought process less obvious (e.g. "If I asked you whether this door lead to freedom, would you say yes?" is really the same as "Are we either in scenario FT or scenario DL?", but it sounds much cleverer).

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.

From the point of view of information theory, when there are no random answers one well-chosen question should always get you exactly one bit of useful information. In the presence of random answers, you have a chance of getting a useless answer to your question, so you get slightly less than one bit per question. By phrasing questions correctly, a truth-teller and a liar become equally useful to you, so the challenge is to ask a few questions at the beginning in order to identify someone who is not a random answerer so that you can ask that person the last few questions and extract the information you are after. In any situation where there are at least as many random answerers as truthtellers/liars, you have little hope, since the random answerers could "randomly" end up acting exactly as if the roles were reassigned with them as all of the truthtellers/liars and the real truthtellers/liars as random answerers (of course in the puzzle you describe, in the bad case where there are as many randoms as truthtellers/liars the answer is just that there are two random answerers, so it is still solvable). If there are more truthtellers/liars than random answerers then you know that with enough questions you can manage things by, essentially, taking the majority opinion (and phrasing questions appropriately to make liars behave like truthtellers). Then you just brute force your way to the most efficient (and cleverest sounding) strategy.

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Taemyr May 21 '15 at 8:05
  • 4
    $\begingroup$ 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. $\endgroup$ – Bob May 21 '15 at 8:18
  • $\begingroup$ 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. $\endgroup$ – zeb May 21 '15 at 8:22
  • $\begingroup$ @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? $\endgroup$ – Taemyr May 21 '15 at 8:26
  • $\begingroup$ 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. $\endgroup$ – zeb May 21 '15 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.