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.
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.
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.
– Sirv Mar 16 '24 at 19:55You 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.
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.
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
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.
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.
