1
$\begingroup$

There are 3 guys, Mr. Honest, that always give the truth answer; Mr. Liar, that always give the false answer; and Mr. Drunk, that gives a random number.

Now: allow you to ask 3 questions, each to be answered by one of them that you could pick up, and of course the questions shall be answerable by simple "Yes" or "No" -- to avoid a Turing machine dead loop.

How to design the 3 questions so you can distinguish them, Mr. Honest, Mr. Liar, and Mr. Drunk?

$\endgroup$
  • 1
    $\begingroup$ Why not ask any person whether he is Mr. Drunk? If you hit him, you have to ask that same question again to the next person and you will be done. Or do you mean random answer instead of random number. $\endgroup$ – Marc Palm Nov 18 '13 at 7:08
4
$\begingroup$
  1. Ask Person 1 "Is Person 2 more likely to be truthful that Person 3?" If the answer is "Yes" then Person 3 is not Mr Drunk, if "No" then Person 2 is not Mr Drunk.

  2. Identify this non-Drunk as ND1, and then ask ND1 a similar question about the other two to identify another non-Drunk ND2. You now know which one is Mr Drunk by elimination.

  3. Ask ND2 "if I asked ND1 whether you are Mr Honest, what would he say?". A "Yes" will tell you ND1 is Mr Honest and ND2 is Mr Liar, while a "No" will tell you ND2 is Mr Honest and ND1 is Mr Liar.

$\endgroup$
  • $\begingroup$ Could u pls explain a bit how you find the way out? $\endgroup$ – athos Sep 28 '13 at 11:37
  • 1
    $\begingroup$ My solution is based on (a) eliminating Mr Drunk and (b) asking a useful question which Mr Honest and Mr Liar will answer the same way. If you are asking for directions, change my third question. $\endgroup$ – Henry Sep 28 '13 at 12:10
  • $\begingroup$ @Henry. Your solution seems flawed. Asking the first question to Person 1 does not guarantee that Person 1 is Mr. Honest. The answer "yes" or "no" could be given by any of the three, so you wouldn't know whether the answer is true or not, or how to derive anything about person 2 and person 3. $\endgroup$ – Cuc Feb 4 '14 at 0:44
  • 1
    $\begingroup$ @Cuc: Perhaps you could give an an example where Person 1 says "Yes" when Person 3 is Mr Drunk. Or an example where Person 1 says "No" when Person 2 is Mr Drunk. The question to Person 1 is "Is Person 2 more likely to be truthful that Person 3?" $\endgroup$ – Henry Feb 4 '14 at 1:00
  • $\begingroup$ @Henry. You got me thinking :-). I went over my own argument again, checking each case and was surprised to find that your conclusions are in fact correct. I was trapped by the case when Person 1 is Mr. Drunk, and realized now that this case is also covered by your solution, since in that case neither Person 3 nor Person 2 is Mr. Drunk (and so, it does not really matter what Mr. Drunk says to derive at a correct conclusion who IS NOT Mr. Drunk) . . . I proceeded to the other two questions and found that your solution is correct after all. Thanks. $\endgroup$ – Cuc Feb 4 '14 at 20:51
1
$\begingroup$

Here is one way to really design the questions. I am assuming that we can distinguish the three persons by sight, that the persons know each others' identities, and that a later question is allowed to depend on the answer of an earlier one.

Let's write $\;T(x)\;$ for "$\;x\;$ is Mr Honest" (who always speaks the Truth), and similarly $\;F(x)\;$ for Mr Liar and $\;R(x)\;$ for Mr Drunk. And let's give the arbitrary names $\;a,b,c\;$ to the three men as we distinguish them.

The 'axioms' underlying this type of puzzle are: \begin{align} \newcommand{\says}[2]{#1\text{ says }\unicode{x201C}#2\unicode{x201D}}\newcommand{\cansay}[2]{#1\text{ can say }\unicode{x201C}#2\unicode{x201D}} (0) \;\;\; & \says{x}{P} \;\Rightarrow\; \cansay{x}{P} \\ (1) \;\;\; & \lnot R(x) \;\Rightarrow\; (\cansay{x}{P} \;\equiv\; T(x) \;\equiv\; P) \\ \end{align}

Principle

First, a principle in many of such "knight-knave problems" is to ask someone a question, and even get information out of them if they are lying. Suppose we want to know whether $\;P\;$ is true, what question $\;Q\;$ must we ask $\;x\;$, and how must we interpret the answer $\;r\;$? Formally, we want to find a $\;Q\;$ such that $$ \says{x}{Q \equiv r} \;\Rightarrow\; (P \equiv r) $$ We avoid the difficult case of drunkenness by assuming $\;\lnot R(x)\;$. Then \begin{align} & \says{x}{Q \equiv r} \;\Rightarrow\; (P \equiv r) \\ \Leftarrow & \;\;\;\;\;\text{"weaken using $(0)$ -- the only thing we know about $\;\says{\cdot}{\dots}\;$"} \\ & \cansay{x}{Q \equiv r} \;\Rightarrow\; (P \equiv r) \\ \equiv & \;\;\;\;\;\text{"by $(1)$ using $\;\lnot R(x)\;$"} \\ & (T(x) \equiv Q \equiv r) \;\Rightarrow\; (P \equiv r) \\ \Leftarrow & \;\;\;\;\;\text{"logic: weaken -- the simplest way to bring both sides together"} \\ & T(x) \equiv Q \equiv r \equiv P \equiv r \\ \equiv & \;\;\;\;\;\text{"logic: simplify; move $\;Q\;$ to the left -- we're solving for $\;Q\;$"} \\ & Q \equiv T(x) \equiv P \\ \equiv & \;\;\;\;\;\text{"by $(1)$ using $\;\lnot R(x)\;$" -- to make the question simpler"} \\ & Q \equiv \cansay{x}{P} \\ \end{align} Substituting for $\;Q\;$ in the above equation, we've proved that for any $\;x\;$ with $\;\lnot R(x)\;$ $$ \says{x}{\cansay{x}{P} \equiv r} \;\Rightarrow\; (P \equiv r) $$ In words: Ask any non-drunk person, "Can you say $\;P\;$?", and Yes ($\;r \equiv \text{true}\;$) means that $\;P\;$ is true, and No means that it is false.

The first question: determinism

In our first question, we want to find a non-drunk person, who answers deterministically, so that from the second question on we can apply the above principle.

Since asking Mr Drunk about himself will not generate any information, it seems we must ask one person about the other. We arbitrarily decide to ask $\;a\;$ about $\;b\;$, trying to find out whether $\;b\;$ is Drunk or deterministic, so whether or not $\;R(b)\;$ is true.

Now, if we already know $\;\lnot R(a)\;$, then we can use the above principle to ask $\;a\;$, "Can you say that $\;R(b)\;$?" An answer of Yes means that $\;R(b)\;$, and that $\;c\;$ is therefore deterministic; and similarly an answer of No means that $\;b\;$ is deterministic.

And now the nice thing: in the other case, if $\;R(a)\;$, then both $\;b\;$ and $\;c\;$ are deterministic, so it does not matter who we choose.

Therefore we can just ask $\;a\;$, "Can you say that that person [we point to $\;b\;$ here] is Mr Drunk?" On Yes, we know $\;c\;$ is deterministic, otherwise $\;b\;$ is. Let's call this deterministic person $\;d\;$.

The second question: truth

For our second question, we'd like to know whether $\;d\;$ is Mr Honest or Mr Liar. So we simply apply our principle, and ask $\;d\;$, "Can you say that you are Mr Honest?" Yes means he is Mr Honest, No means he is Mr Liar.

The third question: randomness

For the third question, all that is left to know is the identity of Mr Drunk. So we ask $\;d\;$, "Can you say that that person [we point to $\;a\;$ here] is Mr Drunk?" Yes -- again by our principle -- means $\;a\;$ is Mr Drunk, No means he is the 'opposite' of $\;d\;$.

With this, we know the identities of $\;d\;$ and $\;a\;$, and therefore the identity of the third person follows.

$\endgroup$
  • $\begingroup$ I propose a clarification. From your explanation, I would rephrase "Can you say that person a is Mr. Drunk?" into: "Can you say: 'Person a is Mr.Drunk'?" Your explanation then follows. - If asked to Mr. Honest, the answer will be yes (obviously). If asked to Mr. Liar, Mr. Liar knows that he can not say "Person a is Mr. Drunk", because it is true, so he will also answer 'yes', to lie about it. Therefore, both Mr. Honest and Mr. Liar answer the same to this question. Either you ask Mr. Drunk and both others are deterministic, or the person who is identified as not Mr. Drunk is deterministic. $\endgroup$ – Cuc Feb 4 '14 at 1:23
  • $\begingroup$ You also showed that three questions can be found independently of what the answers to them are. Clever. $\endgroup$ – Cuc Feb 4 '14 at 1:25

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.