5
$\begingroup$

There are 2000 treasures, among which only one is real and the others are fake. There are also 2000 knights, among whom one always tells the truth while the others always lie. You can ask the knights questions to which they can only answer 'yes' or 'no'.What is the minimum number of questions needed to find out which one is the real treasure?

I'm thinking about binary search then that's about $log_2 2000$ rounds. But I'm not sure about how to make use of the knights.

$\endgroup$
2
  • 3
    $\begingroup$ Welcome to Puzzling, take our tour! Could you please provide proper attribution for this question? $\endgroup$
    – bobble
    Mar 13 at 13:46
  • $\begingroup$ @bobble Thanks for your reminder. But I just heard it from a friend so I'm not sure about the source. $\endgroup$
    – Emma
    Mar 14 at 1:19

6 Answers 6

12
$\begingroup$

As several comments have pointed out, there is no need to identify the truthful knight. As long as the knights themselves know about the lying setup, this can be done by asking a single knight (or a random knight each time) 11 questions, all taking the form:

If I asked the most truthful of the other knights, would they say the treasure is in this half?

The treasure will always be in the other half, no matter whether you are asking a honest or lying knight

This can be used as a binary search as you suggest, giving $\log_2(2000)$ or 11 questions in all cases.

$\endgroup$
2
  • $\begingroup$ I would argue that if you ask the truthful knight anything about "the most truthful of the other knights" he wouldn't be able to answer because there is no such knight, because they are all equally truthful. $\endgroup$
    – Ivo
    Mar 15 at 12:43
  • $\begingroup$ What is the biggest number out of these: {1, 3, 2, 3}? The maximum of a group can be perfectly well defined even if it is not unique. If the lying knights would answer in different ways the truthful knight's answer would not be well defined, but they would all answer with the same lie so the truthful knight will answer with that same lie. $\endgroup$
    – Sirv
    Mar 16 at 19:55
3
$\begingroup$

You can ask the same question of two knights at a time. Split the pile into two halves and ask any two knights "is the treasure in this half?" about the same half. If they both answer the same, they are both lying and you know what the truth is. Split the half that contains the treasure and one of them (knowing they lie) if one of the new smaller piles contains the treasure. If your first pair of knights gives different answers, you can ask any third knight the same question, to work out which of your pair is lying and which is telling the truth. After the first question, you only need ask one knight at a time to continue your binary search.

If you didn't ever find the truth telling knight, you'd ask 2 to get it to 1000, then 1 each to get it to 500, 250, 125, 63 (I'm assuming the treasure is in the larger group to keep choosing the worst case), 32, 16, 8, 4, 2, and finally to 1 for a total of 11 questions.

If otoh you got diverging answers on the first go, you'd ask 3 to get it to 1000, then 1 each to 500, 250, 125, 62 (going best case this time), 31, 15, 7, 3, and again being lucky the first of those three is the treasure for a total of 12.

So if your definition of minimum includes good luck, 11. If it means minimum even with the worst luck, 12.

$\endgroup$
2
  • 3
    $\begingroup$ I don't think this is quite right. You don't need to find the truth-telling knight at all - a consistent liar is just as useful for finding the real treasure. Once you know the status of any single knight, you can just use that knight to binary-search the remaining pile. And you can identify one knight by questioning at most three of them. $\endgroup$
    – fljx
    Mar 13 at 12:26
  • 2
    $\begingroup$ Per a comment on the other answer from Jaap Scherphius, a reliable liar is just as reliable as a reliable truth teller, so if you ask any one knight "Is 1+1=2?", you'll conclusively identify him as either a truthteller or a liar, and can then proceed with the binary search for the treasure, finding the answer in a total of thirteen questions. $\endgroup$ Mar 13 at 15:03
2
$\begingroup$

Twelve questions are enough. and several strategies can be used.

- Ask a verifiable question to a knight (e.g. are you a knight?), and then ask 11 binary search questions to that knight.
- Ask a question about other knight(s) (e.g. knight1: Is knight2 a liar? On no they are the same type and thus liars, and on yes of different type and thus all others are liars. Then ask 11 binary search questions to a known liar.

$\endgroup$
1
$\begingroup$

3 questions will do I think? (Assuming you ask all knights at once, otherwise it's in the 1000s)

Assign each knight to a treasure. Ask each knight if they're holding the real treasure. From there there's a 1/2000 chance you'll get 2000 yes's and a 1999/2000 chance you'll get 1998 yes's and 2 no's.

In the 1/2000 case, ask each knight to pass their treasure to another knight, so that each knight holds exactly 1 treasure again. Then ask again.

Now you have 2 no-candidates, one of them is a lying knight holding the real treasure, the other one is telling the truth and holding a fake. To find out, have them both pass the treasure to any knight you know is lying, and ask the new holders. The answer that didn't change is the real treasure

$\endgroup$
1
  • $\begingroup$ I think that would be counted as multiple thousands of questions. I don't think you are allowed to ask one question very loudly and then receive 2,000 answers. $\endgroup$ Mar 15 at 14:57
1
$\begingroup$

The number of questions you need to ask to take possession of the real treasure is only

one

And this is how this is possible

Chose any one knight and ask:
"Is there an odd number of true statements among A: "you are a truthteller", B: "you answer with yes" and C: "you will offer me the treasure" ?

- If it is a truth-teller who says yes, the count must be odd. A is true, B is true, C must be also true.
- If it is a truth-teller who says no, the count must be even. A is true, B is false, C must be true.
- If it is a liar who says yes, it is a lie, the count must be even. A is false, B is true, C must be true.
- If it is a liar who says no, it is a lie, the count must be odd. A is false, B is false, C must be true.

In every case the conclusion is that C is true, so you will be offered the real treasure. You just need to accept, thank you very much.

Note that there is no paradox. There is no situation that has no valid outcome. It is just that in order to remain true to his character, pathologic truth-teller or liar, the knight has no choice but to offer you the real treasure.

$\endgroup$
2
  • $\begingroup$ This is neat, but you've introduced a new capability for the knights - to offer (or point out) the one real treasure among the fakes. The question only grants them the ability to answer yes or no questions about it such as "is this the treasure?" $\endgroup$ Mar 16 at 13:41
  • $\begingroup$ Yeah... it is a somehow out-of-the-box answer. But not completely wrong either. $\endgroup$
    – Florian F
    Mar 16 at 22:46
0
$\begingroup$

As some commenters have implied, there is a solution with

only 11 questions,

fewer than the other answers have proposed.

The general structure is a binary search just like all the other answers so far: keep dividing the remaining candidate treasures into two sets and asking whether the real treasure is in a particular one of the two sets. This requires 11 questions in total since $2^{10} < 2000 \le 2^{11}$.

However,

We don't need to ask a 12th question at any point. At each stage, simply call out to the entire assemblage of knights, "Is the real treasure in this pile?" We will hear a resounding unanimity of lying answers (maybe with a tiny lone voice of noble opposition somewhere, but we don't care), and we simply choose the other pile to split at the next stage.

$\endgroup$
2
  • 1
    $\begingroup$ I believe the assumption is that asking the same question to multiple knights counts as multiple questions, otherwise there would be no point to having the lying vs truthing knights as you discovered. $\endgroup$ Mar 13 at 21:31
  • $\begingroup$ I misinterpreted some other answers which led me here ... anyway the basic idea was implemented better by Sirv, so I'll just let this stand and upvote theirs. $\endgroup$ Mar 14 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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