14
$\begingroup$

I haven't seen this kind of liar type before, so here is a simple puzzle as a means for a trial run. In particular, I did check it myself, but with new mechanics it's easy to miss something (I hope I didn't), so don't be angry if the puzzle doesn't have a proper answer or if it can be easily circumvented.

There are three persons A, B, C. A and B say truths or lies randomly (i.e., they first construct an answer and then they flip it randomly, only yes/no questions, circular dependencies are invalid). C tells the truth or lie depending on whether A and B told truths or lies in their last respective answers, but we don't know how exactly (there are $2^4$ possibile strategies for C). Each time you ask a question, all three answer it in order A B, C. How many yes/no questions do you need to ask to know which of the two roads, left or right, leads to salvation?

Also, any suggestions of improvements are welcome and will be greatly appreciated.

Edit:

  • Just to make it clear, C's strategy is static, i.e., he does not change it. We do not know (at least initially) which one it is, but there is only one that he is using.
  • We cannot ask about things that are undecided in the future (for example A's or B's coin flips), but we can ask about things that are fixed, in particular, things that are in the past (it won't create any circular dependencies). To give an example, when C is answering his question, A and B have already said their replies and they cannot change them anymore. In other words, their answers became fixed, and the question could depend on that information, given that it doesn't cause any contradictions or circular dependencies when A and B are answering it.
$\endgroup$
  • $\begingroup$ What do they answer when they lie but the question has more than two possible answers? For example, what would be a lie for a question like "2+2"? Any real number different than 4? $\endgroup$ – Pere Oct 3 '16 at 11:44
  • $\begingroup$ @Pere They handle only yes/no questions. Thanks for noticing! $\endgroup$ – dtldarek Oct 3 '16 at 11:46
  • $\begingroup$ I feel like you cannot get information from this system because it is basically a coin flip. $\endgroup$ – Trenin Oct 3 '16 at 12:22
  • 1
    $\begingroup$ @EngineerToast One possibility is $\{\{T,T,T\},\{T,F,T\},\{F,T,T\},\{F,F,T\}\}$. i.e. "C always tells the truth". There are 15 more ways that the function of C can be determined. $\endgroup$ – Trenin Oct 3 '16 at 12:34
  • 1
    $\begingroup$ Turned out to be a pretty good puzzle. Nice job! $\endgroup$ – Trenin Oct 3 '16 at 18:29
13
$\begingroup$

My interpretation of the problem is that each of A, B, and C always answer every question in that order, and C is aware of their own deterministic lying. Under these conditions: one question:

Is exactly one of the following true: 1) you know you are going to lie now, 2) the left door is safe?

C's answer to the question is the truthful answer about the door's safety.

Explanation:

A and B don't know whether they are going to lie or not, so their answers are just random no matter what we ask. However, C's lying is determined by the previous answer, so C does know whether they will lie or not, and we can extract the correct answer from them. (Indeed, the only real trick is wording the question so that A and B can also answer it.)

The exclusive-or ("exactly one is true") negates C's (lying) answer if and only if they are going to lie, thus making their answer always truthful about statement 2, i.e., the safety of the left door.

(Statement 1 could also be rephrased "you are C and you know you are going to lie" if it is for some reason considered unclear whether A and B know about their lying. The "you are C" can also be phrased in different ways if they do not recognise themselves as "C", e.g., "you are the third person present to answer this question".)

The cases for C's answer:

  • 1) false (= telling the truth), 2) false => neither is true => answer "no"
  • 1) false (= telling the truth), 2) true => true => exactly one is true => answer "yes"
  • 1) true (= lying), 2) false => exactly one is true => lie "no"
  • 1) true (= lying), 2) true => both are true => lie "yes"

$\endgroup$
  • $\begingroup$ Nice wording. Almost what I intended, to break the dependency completely I wanted to use "from the last answer of B you have heard and the answer or A that came immediately before that you know C can infer he will lie this round". $\endgroup$ – dtldarek Oct 3 '16 at 16:58
  • $\begingroup$ Hmm; this sounds familiar.  Oh, yes; it’s almost identical to this answer. Not that there’s anything wrong with that. $\endgroup$ – Peregrine Rook Oct 3 '16 at 17:27
  • 1
    $\begingroup$ @PeregrineRook In this variant I guess the "clever" part is making the same question answerable by all three. Whereas the other answer could (as you pointed out) use the standard nested question, this one could not. $\endgroup$ – Arkku Oct 3 '16 at 17:48
  • $\begingroup$ @Arkku Correct. I was forgetting that statement 1 affects what he says. If he knows he is going to lie, he ends up lying. $\endgroup$ – Trenin Oct 3 '16 at 18:28
  • $\begingroup$ Great answer. In the end it is equivalent to ask "if you are going to lie tell me if the left road is unsafe, but if you are going to tell the truth tell me if the left road is safe", but it works around the obvious fact that it would be seen as cheating. $\endgroup$ – Pere Oct 4 '16 at 8:48
1
$\begingroup$

Assuming that you now who are A, B and C guards and that the questions can be different for each guard, the answer is:

You need 5 questions to each guard at worst.

If we could ask direct questions to each individual (which is precluded by statement), the reason would be:

Answer of C is truth or a lie deterministically depending on if A and B have lied. Since there are only 4 combinations of truth/lie for A and B (both lie, A lie B truth, A truth B lie and both truth), you can do the following:
Ask to A and B a question with well known answer. For example, "does 1+1 equals 2?".
Then ask C the same question (or another question with well known answer). Now you know if C lies for a certain combination of A and B. For example, if they answered A:yes B:no C:no, you know that when A tells the truth and B lies, C lies. Write it down.
Ask another (or the same) question to A and B. If the combination of truth/lie is the one you know, you know if C is going to lie or not and you can ask him about the right road. If the combination is not the one you know, then you just ask C a known answer question and you will know another combination.
Since there are just 4 combinations, or one of them is repeated before the 5th round of questions (and therefore you know the exit), or the 5th question is going to be a repetition of a known combination and you can ask C about the exit.

Then, one possible strategy is try to get the same information as if we could ask direct questions, by making complicated question with different answers according to guard and situation. In fact, there are a lot of ways to ask a question in the way "If you are A or B answer this, and if you are C answer that".

The question would be like "If you are A or B, tell me if 1+1=2. If you are C and A and B have answered [put here the known combinations, like (yes,no), (no,no)...] tell me if the road on the right leads to salvation, but if A and B have answered [put here the unknown combinations, like (no,yes), (yes,yes)...] tell me if 1+1=2.
Having questions using "if" could be seen as an unfair workaround, but there are other ways to do the same without using "if". For example, we can use arithmetic functions as module, maximum or absolute value to make a question that included some computations using the letter of the guard that gave us the desired answer.

$\endgroup$
  • 4
    $\begingroup$ "Each time you ask a question, all three answer it in order A B, C". I would say that precludes this strategy since you cannot direct a question to an individual. $\endgroup$ – Trenin Oct 3 '16 at 12:08
  • 3
    $\begingroup$ If you could direct questions to them, then you could accomplish this in 4 questions. Ask A anything, ask B anything, and then ask C "Is 1+1=2?" and then ask C "Is the left door safe?". If he lied the first time, he will lie again since his answer is only dependent on the last answer of A and B. $\endgroup$ – Trenin Oct 3 '16 at 12:10
  • $\begingroup$ It might even be possible in two questions depending on whether or not C has a default state (i.e. does he know what to do if he doesn't hear an answer from A and B first). If so, then you simply ask C the two questions from above. If he lies in the first he will lie in the second. If he tells the truth in the first, he will tell the truth in the second. $\endgroup$ – Trenin Oct 3 '16 at 12:12
  • $\begingroup$ @ Trenin You are right that the statement precludes asking direct questions to individuals. I'll try to fix that. $\endgroup$ – Pere Oct 3 '16 at 12:14
  • $\begingroup$ @Pere Nice stragy, I think you can modify it to work in my setting (i.e., you ask a question to all) as well by some logic manipulation. $\endgroup$ – dtldarek Oct 3 '16 at 12:19
1
$\begingroup$

You only need

one question.

The trick is to use the "What would you say if I asked you?" device that forces liars to answer in the same way as truth-tellers.

"If my question to you this round were 'Is the right road safe?', would you say yes?" If the right road is safe, an C will say yes whether or not they're lying this round, otherwise C will say no.

$\endgroup$
  • 2
    $\begingroup$ I don't think that works, because you're proposing a hypothetical alternate past for which C doesn't know what A and B would have said. I also don't think you can stipulate what A or B say without falling afoul of the circular dependency clause $\endgroup$ – Sconibulus Oct 3 '16 at 16:36
  • $\begingroup$ The question only asks C to consider what C would say if C was asked the question, no alternate past answers for A and B are required. $\endgroup$ – Ninety-Three Oct 3 '16 at 16:51
  • $\begingroup$ This approach trivially defeats ALL tests of this nature, which means it probably is disallowed. $\endgroup$ – Dark Matter Oct 3 '16 at 16:52
  • 1
    $\begingroup$ Per my reading of the propmt, C doesn't know how to answer that, because A and B didn't answer that question, they answered a different question. $\endgroup$ – Sconibulus Oct 3 '16 at 16:53
  • $\begingroup$ Your question has circular dependency within A, in particular A may not know the flip until the end of A answering that question (i.e. just before B starts). Although for C only it is ok. $\endgroup$ – dtldarek Oct 3 '16 at 17:14
0
$\begingroup$

The real key is "C". Is he doing an "AND", an "OR", a "NAND", a "NOR"? Presumably he's not just echoing "A" or "B" because of the phrase "A and B" above.
https://en.wikipedia.org/wiki/NOR_logic

Edit: Other types of logic gates are possible, "mimic A", etc, so that increases the number of questions needed to eval what "C" is doing.

One problem is...

You might need an infinite number of tests to figure out what 'C' is doing in order to evaluate him. Say if "A" and "B" always 'randomly' get "T" then "C" would be hard to evaluate. Let's ignore this and assume you get some sort of random distribution. So (ideally) you ask '2+2=4' four times and figure out "OR" or whatever.

Example:

You know what "C" is doing, then you ask "is this the gate to freedom". If "B" disagrees with "A" then one is a liar and one is telling the truth. That means an "OR" C's answer tells the truth, while an "AND" C would be a lie, and so on. However if "A" and "B" agree with each other then you need a new question because "C"'s answer only adds meaning if they disagree. (This assumes C's logic cares that A and B disagree)

So...

I put the Minimum number of questions at five (4 for A and B), the max is infinity.

$\endgroup$
  • 2
    $\begingroup$ I don't think you can ask "Would a truthful A say..." because how would $A$ answer? He doesn't know the result of his coin flip until it is done and he must come up with an answer before the coin flip. I think the "circular dependencies are invalid" from the question makes this type of question invalid. $\endgroup$ – Trenin Oct 3 '16 at 12:49
  • $\begingroup$ IMHO this criticism applies to anything "A" could say, however the logic works without that so I'll edit the post to remove it. $\endgroup$ – Dark Matter Oct 3 '16 at 12:57
  • $\begingroup$ It's not clear from what you have written, so just in case, there are more strategies for C than just AND, OR, NAND and NOR. $\endgroup$ – dtldarek Oct 3 '16 at 13:11
  • $\begingroup$ Update to post to reflect other possibilities... which increases the min number of questions. $\endgroup$ – Dark Matter Oct 3 '16 at 13:17
0
$\begingroup$

The answer to this problem is simpler than you might think:

There is no guaranteed solution.

Proof:

You simply cannot identify C if the function it uses to tell the truth or to lie is uniform, i.e. it returns "tell the truth" for two of the possible combinations of A and B and "lie" for the other two combinations. Thus, asking questions with known answers will show a uniform distribution of truth and lie for all three people.

But:

If, however, you are lucky enough that C's function is not uniform, then simply ask a lot of known (obvious) questions and on the long term you would notice that the true/false curve goes farther away from 50% only for one of them. That's C. Then it becomes simple.

$\endgroup$

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.