13
$\begingroup$

There are 3 boxes, only one of which contains a treasure.

The guardian will only answer you truthfully once, the other three times he will lie.

You may ask 4 YES or NO questions.

Which questions should you ask, to know which box contains the treasure?

$\endgroup$
  • 3
    $\begingroup$ Does it have to be exactly four questions? Because it can be done in one or two. $\endgroup$ – Longspeak Sep 14 '17 at 16:36
  • $\begingroup$ @Longspeak : You may succeed with two questions, but with only one I would be very surprised... $\endgroup$ – Evargalo Sep 15 '17 at 12:53
  • $\begingroup$ 4 is maximum... $\endgroup$ – Legionar Sep 17 '17 at 12:57
24
$\begingroup$

Ask three times of box 1. If the answer changes, you know about box 1. If not ask of box 2. This question has a known truth/lie answer, so you know which box.

$\endgroup$
  • 3
    $\begingroup$ Knowing about box 1 does not require the answer to change, that just tells you if the answer to box 2 is a truth or lie. Box 1 is just the opposite of the answer that was given multiple times. $\endgroup$ – Apep Sep 14 '17 at 14:07
11
$\begingroup$

As JonMark said, you ask 3 times if the item is in box 1.

There's 4 possible scenarios here:

You get (1) YYN/YNY/NYY, (2)NNY/NYN/YNN, (3)YYY, (4)NNN

In cases 1 and 2

You know that the answer that deviated is the truth. So in Scenario 2 we're done. In scenario 1 we know that it's not 1, and the next question is a lie.

In cases 3 and 4

You know that all answers were lies, in 3 it's not box 1, in 4 it is. You know that the next question is true.

In all cases

You ask if it's in box #2, if you came from case 1, you know that the answer that's given is false. If you came from case 3 the answer you get is true, either way you know the answer.

$\endgroup$
  • 1
    $\begingroup$ A couple of quibbles on your writeup. You should explicitly state that the number/ratio of Y/N answers are what's important, not the order, which is how it reads currently. In your conclusion you state that you ask a "WH" question, which is not allowed. $\endgroup$ – feelinferrety Sep 14 '17 at 16:48
  • $\begingroup$ @feelinferrety Fixed it. $\endgroup$ – DrunkWolf Sep 14 '17 at 17:21
  • $\begingroup$ Great. Now I have to quibble that this is pretty much a longer version of the already-accepted answer, and even references it. We like to discourage folks from clogging up the site with repeat answers. Although in your case, the additional level of detail is appreciated, so I'm really not going to bug you about it any further. $\endgroup$ – feelinferrety Sep 14 '17 at 17:50
8
$\begingroup$

A sillier one (but still works):

First, ask the guardian if they're going to tell the truth on their fourth answer.

Then,

If they say no, either they're telling the truth or they will be on the fourth, so your second and third guesses can be used to find the box full of treasure.

Or else,

If they say yes to the first question, then 1 and four are both lies, so ask something trivial on the second ('Is the sky blue?') to establish the veracity of their second, and thus their third, answer, then use three and four to find the treasure box.

$\endgroup$
  • $\begingroup$ I would ask "is $1 + 1 = 2$?" because the sky might be cloudy, or it might be night etc. $\endgroup$ – wizzwizz4 Sep 14 '17 at 16:45
  • 1
    $\begingroup$ You could also ask if the first answer was the truth for the second question in the second scenario, because you've already established its veracity. $\endgroup$ – Apep Sep 14 '17 at 16:51
  • $\begingroup$ Your writeup is not very clear as the wall of text it currently is. Could you separate out the choices by question number? I feel like there may be a flaw in your logic, but can't tell due to a couple of conflicting number labels. $\endgroup$ – feelinferrety Sep 14 '17 at 16:51
  • $\begingroup$ a very prety way, instead of just asking three times the same question, asking if the first question is true for the second is a good idea also $\endgroup$ – Neil Sep 15 '17 at 14:17
  • $\begingroup$ He might pause indefinitely because he doesn't have a plan for the truthfulness of his answers and you get no answers for any questions. $\endgroup$ – user2617804 Sep 17 '17 at 9:50
4
$\begingroup$

Let's number boxes 1, 2, 3.

I'll ask her twice if one of 1 & 2 treasure.

Now following cases can occur:

She flips her answer. Then we know next two answers must be false. After this I ask her if 3 is treasure. If she says no then 3 is the treasure, otherwise one of 1 & 2 is. My last question would be if 1 is treasure. If she says yes then 2 is the treasure otherwise 1.

Second case is that,

She doesn't flip her answer. Then she must be telling false both the times. If she says no then the treasure is in 1 & 2. Else it's in 3. If treasure is in 1 or 2 then again ask her if treasure is in 1 & 2. If she flips the answer then she must say the false for next answer and if she's doesn't then she must tell true. Now since we're deterministic about the kind of answer, we can ask her about 1, if she's about to say true and says yes then it is the treasure box else it is 2. Same follows if she's about to say false.

$\endgroup$
  • 1
    $\begingroup$ I'm assuming you ask your first question twice? :) $\endgroup$ – DrunkWolf Sep 14 '17 at 14:24
2
$\begingroup$

Simply ask them a question formatted like this:

If I instead asked you "does box 1 hold the treasure", would you say yes?

Suppose they are lying:

Then they would have lied to the question you asked instead. A lie about a lie is the truth. So their answer to this compound question is the truth to the quoted question.

Suppose they are telling the truth:

Then the answer to this compound question is also the truth.

If there where 16 boxes I could find the one with the treasure using this technique with 4 questions.

Stand with half the boxes on your left, and half on your right. Using the above trick, determine if the treasure is on your left or right "If I asked you instead of this question 'is the treasure to my left', would you answer yes?". Using this, N questions can pin down where the box is among 2^N boxes.

$\endgroup$
  • 3
    $\begingroup$ The guard does not need to have a fixed pattern of truths/lies, per the OP. E.g. The guard's supervisor might have told him/her to "always tell the truth on the first question, unless it is a question about box 1". Then, if box 1 does have the treasure, he/she will answer "No." to your twisty question (and still tell the truth). $\endgroup$ – Bojidar Marinov Sep 16 '17 at 14:11
2
$\begingroup$

If you allow recursive questions, this can always be done in 1 or 2 questions:

Q1. Would you answer yes if my first question were does box 1 contains the treasure?

If answer 1 is "yes", then the treasure is in box 1.

If answer 1 is "no", then ask:

Q2. Would you answer yes if my second question were does box 2 contains the treasure?
If they say "yes", then the treasure is in box 2.
If they say "no", then the treasure is in box 3.

Because:

By adding recursion, either:
if an answer is honest, truth is preserved
if an answer is dishonest, then falsehood is reversed - a lie about a lie produces the truth.

Without recursion it will always take between 2 and 4 questions. It cannot reliably done in less:

Ask twice if box 1 contains the treasure.
If the answer is "no" both times, then the treasure is in box 1.

If the answer is "yes" once and "no" once, then ask once if the treasure is in box 2.
The answer will be honest.

If answer 1 and answer 2 were both "yes", then ask for a third time if the treasure is in box 1, and then ask if the treasure is in box 2.

If the third answer is "yes", then the fourth answer is a lie. If third answer is "no", then the fourth answer is the truth. Proceed accordingly.

Because:

If we get lucky, we get the answer after 2 questions. If not, there is a chance we will get it in 3 questions. But there is no combination of non-recursive questions and boxes that will tell us which box contains the treasure, for all combinations of box-contains-treasure and answer-is-honest.

There are 12 possible combinations: 3 possibilities for the box and 4 possibilities for the honest answer. The most optimal search algorithm will halve the search space each time a question is asked:

Start: 12 possibilities
After Q1: 6 possibilities
After Q2: 3 possibilities
After Q3: 1.5 possibilities (i.e. sometimes 1, sometimes 2)
After Q4: 1 possibility

$\endgroup$
  • 1
    $\begingroup$ Your recursive question does not quite work. You have no guarantee that the guard chooses which question to answer honestly is independent on which question is asked. $\endgroup$ – Taemyr Sep 17 '17 at 5:44
  • $\begingroup$ You are correct. Which is only part of the reason I said "if...". $\endgroup$ – Ben Aveling Sep 18 '17 at 16:23
  • $\begingroup$ A nitpick, but your first question may or may not be a yes-or-no question - it depends if "yes or no question" means "a question that can only be answered in the affirmative or negative" or "a question that can only be answered with the words 'yes' or 'no'". "What would you answer" qualifies as the second but not the first. "Would you answer 'yes'" is equivalent here and doesn't have the ambiguity. $\endgroup$ – Oosaka Sep 19 '17 at 17:17
  • $\begingroup$ @Rozenn. Fair point. I've reworded it to be more strictly boolean. If you want to split the nit one more time, then I could have said "answer in the affirmative" instead of "say yes", but I think "say yes" is clearer to the reader. And neither construction addresses Taemyr's observation anyway, which is why I prefer the 3 to 4 question construction. The real problem with the recursive question, is that it is actually two questions in one. That's either clever, or cheating. Given the challenge is to do it in 4 questions, I feel it's cheating, but I'll let the reader decide. $\endgroup$ – Ben Aveling Sep 20 '17 at 13:57
1
$\begingroup$

Ask twice if the treasure is in box #1.

There are now 3 possible scenarios.

Once Yes, Once No

You know now that the guardian has lied once and spoken the truth once, or the answers would be the same.

You can now use the knowledge that the Guardian will lie on the next two questions to determine the box with the treasure.

Twice No

You know now that the Guardian has lied twice, or you would've gotten two different answers. Since the Guardian lied no, you know that the treasure is in fact in this box.

You're done.

Twice Yes

You know now that the Guardian has lied twice, or you would've gotten two different answers. Since the Guardian lied yes, you know that the treasure is not in this box.

Proceed by

asking once more if the treasure is in box #1.

If the Guardian answers yes, you now know that the final and fourth answer will be truthful, which you can use to choose between boxes #2 and #3.

Likewise, if the Guardian answers no, you know that the final answer will be a lie again, which you can use as well.

$\endgroup$
1
$\begingroup$

The problem with the absolute yes/no, true/false dichotomy is it's easy to beat with a properly phrased hypothetical question instead of the actual question. You don't even need to know if the answer/answerer is lying or telling the truth.

Question #1:

"If I were asking you right now if Box 1 had the treasure would you answer yes?"

Case 1 - Treasure in Box 1, answer is truth: He answers yes to this question, because if you were really asking if the treasure is on box 1, he'd answer yes.

Case 2 - Treasure in Box 1, answer is lie He answers yes to this questions, because if you were really asking if the treasure is on box 1, he'd answer no.

In either of these cases, you know the treasure is in Box 1, and you are done.

Case 3 - Treasure not in box 1, answer is true He answers no to this question, because if you were really asking if the treasure is on box 1, he'd answer no.

Case 4 - Treasure not in box 1, answer is a lie He answers no to this question, because if you were really asking if the treasure is on box 1, he'd answer yes.

In either of these cases, you know the treasure is not in Box 1. In this case, you repeat the same question for Box 2. Yes will mean the treasure is in box 2, and no will mean box 3.

$\endgroup$
  • 2
    $\begingroup$ How do you know that the truthness of the first answer isn't changed by the number of vowels in the question, or something like that? Then your questions wouldn't help. $\endgroup$ – boboquack Sep 16 '17 at 8:19
0
$\begingroup$

1st question "are you telling a truth now?" (they are forced to answer yes and truthfully to prevent logical inconsistency.(not quite sure on the yes but lying case) anyhow if you'll allow that:

then:
2nd question "is it in box 1" 3rd question "is it in box 2" 4th quesiton "is it in box 3"

Since 2nd 3rd and 4th questions are lies the box become obvious -the no answer reveals the box.

$\endgroup$
  • $\begingroup$ Anybody who speaks consistently will answer “yes” to the question “are you telling the truth?” — a liar would be lying, but so what? You might want to read up on the logic of “truth / lie”-type questions. $\endgroup$ – Peregrine Rook Sep 14 '17 at 22:55
  • $\begingroup$ i guess that question only has a truth or lie aspect in the answers mind. Yes I think you are right Peregrine Rook $\endgroup$ – Andrew w Sep 14 '17 at 23:05

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.