7
$\begingroup$

You've learned that there's treasure buried somewhere on a small island, but not exactly where. The island is a perfect circle with a radius of 25 meters. There are 15 islanders there, one of whom is a joker and the rest of whom are knights. (As usual in these kinds of puzzles, knights always tell the truth, and jokers can answer however they want.) All of the islanders know who the joker is and where the treasure is buried. If you can only ask each islander one yes/no question, and you can only dig up one square meter of the island, how can you guarantee that you retrieve the treasure?

Bonus 1: Is there a way that works even if the islanders don't know who the joker is?

Bonus 2: Is there a way that works if you have to ask all 15 questions before hearing any of the answers?

To preemptively close some loopholes:

  • The treasure is a single point with negligible area.
  • If you make any of the islanders' heads explode by asking them a question that they can't answer with a yes or a no, you'll be kicked off of the island without being able to dig anywhere.
Improve this question
$\endgroup$

4 Answers 4

Reset to default
10
$\begingroup$

Yes to all.

An island of radius 25 has an area of 1963.5m² < 2^11.
Divide the island into 2048 regions each with area < 1m².
Make a (15,11) Hamming code.
Give each area one of those codes.
For each bit, draw a map where regions with a 1 in that bit are colored.
Ask the nth islander "Is the treasure buried in an area that is colored on this map?"

Improve this answer
$\endgroup$
3
  • $\begingroup$ Best and the easiest answer to prove $\endgroup$
    – justhalf
    Sep 11, 2022 at 10:52
  • $\begingroup$ how does this override or negate the joker answers? If it's so easy to prove, why isn't it explained at all? $\endgroup$
    – Kate Gregory
    Sep 12, 2022 at 1:52
  • 1
    $\begingroup$ @KateGregory Hamming codes are a standard error correction method. It is obvious once you know what they are that this method works. I assume most people here have encountered them before, that is why it isn't explained further. If you want further information there are many good resources available online. (I think 3blue1brown has a video on them if you want a specific reccomendation) $\endgroup$
    – Fishbane
    Sep 12, 2022 at 2:12
2
$\begingroup$

I will go with 2 questions.

The first question is to rule out the joker.

Choose any 3 people A, B and C. Point at A and ask to B: "Is this the joker?".
If the answer is yes, then A or B is the joker. Choose C for the next question.
If the answer is no, then B cannot be the joker. If he were, A would be a knight and answer yes. So choose B for the next question.

You have identified a knight. The second question is to locate the treasure.

To the knight you ask: "Will you reply standing on the spot of the treasure or reply negatively? You might want to move to a different location before you answer.".
If the knight is not standing on the spot of the treasure, he cannot answer because the question boils down to "Will you reply with 'no'". So the only way for him to answer is to first move to the spot where the treasure is burried and answer 'yes'.

Bonus 1 and 2

You can ask just the 2nd question but to 3 people. Use the majority answer.

Improve this answer
$\endgroup$
4
  • $\begingroup$ If the Knight chooses not to move, his head will explode when he tries to answer. And I never said any of them had any sense of self-preservation. $\endgroup$
    – Joseph Sible-Reinstate Monica
    Sep 10, 2022 at 20:53
  • $\begingroup$ No, no, no! His head will explode "if he can't answer with a yes or a no". But he can answer. But I agree this is still a loophole. $\endgroup$
    – Florian F
    Sep 10, 2022 at 20:57
  • $\begingroup$ Here's a loophole in your loophole: I gave the criteria to be kicked off the island, not the criteria for heads exploding (since that's implicit in these kinds of puzzles by now). So in your case, the knight's head explodes but you get to stay on the island. $\endgroup$
    – Joseph Sible-Reinstate Monica
    Sep 10, 2022 at 21:03
  • $\begingroup$ Maybe they have no sense of self-preservation. But you claimed "knights always tell the truth". How can a knight tell the truth if his head explodes? $\endgroup$
    – Florian F
    Sep 10, 2022 at 21:12
1
$\begingroup$

Main:

The area is 1964 square meters when rounded up to the smallest integer, which can be reduced to 1 or less with 11 binary searches. The remaining 4 questions are more than enough to identify more knights:

1. Take one of the islanders, and divide the rest into two groups of 7. Ask the chosen islander if the joker is in the first group. If they say yes, either they're telling the truth (therefore not the joker) or they're lying and are the joker. If they say no, they're telling the truth, and the joker is either themself or among the second group, or they're lying and are the joker. Now you know which group only consists of knights.

2. Take the group not guaranteed to consist of only knights, pick one, split the rest into two groups of 3 and ask the odd one out if the joker is among any given 3 people from the remaining 6. Now you can identify 3 more people as knights.

3. Repeat 2 for the other group of 3 (two groups of 1, ask the odd one out). Now you can identify 1 more person as a knight.

4. Use these 11 identified knights (7+3+1) to binary search the entire area.

Bonus 1:

There are 2^15 different answer outcomes, and 2^11*(15+1) different truth and location outcomes, so it's doable.

Bonus 2:

If the main version is solvable, so is this one.

Improve this answer
$\endgroup$
5
  • $\begingroup$ "either they're telling the truth (therefore not the joker)" Jokers can tell the truth. I don't think anything else in your answer depends on that conclusion, though, so I think it's still correct overall. $\endgroup$
    – Joseph Sible-Reinstate Monica
    Sep 11, 2022 at 20:56
  • $\begingroup$ In that case, if they're telling the truth, the joker is in the first group of 7, meaning they're not the one. $\endgroup$
    – Nautilus
    Sep 11, 2022 at 21:03
  • $\begingroup$ I just realized there's a flaw in this answer that seems to completely break it. In step 2, one of the remaining 8 people is the one you already asked a question to in step 1. If that person ends up being one of the 11 knights, then you'll be one question short once you get to step 4. $\endgroup$
    – Joseph Sible-Reinstate Monica
    Dec 19, 2022 at 5:28
  • $\begingroup$ OK, fixed then. $\endgroup$
    – Nautilus
    Dec 25, 2022 at 21:33
  • $\begingroup$ Your new method does indeed work. $\endgroup$
    – Joseph Sible-Reinstate Monica
    Dec 25, 2022 at 21:48
-2
$\begingroup$

Yes to all:

Divide the island into 32 regions, each somewhat less than one square meter, labeled with binary numbers in any order (00000, 00001, 00010, ..., 11111). Share this information with the islanders.

Ask the first three islanders "Is the treasure in a region whose first binary digit is a 1?" At least two will agree, and are telling the truth.

Ask the next three islanders "Is the treasure in a region whose second binary digit is a 1?" And so on.

This may not identify the joker (if they happen to tell the truth), but it will identify a single region smaller than one square meter and guaranteed to contain the treasure.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ The island has a radius of 25 meters, not an area of 25 square meters. $\endgroup$
    – Joseph Sible-Reinstate Monica
    Sep 10, 2022 at 23:42

Your Answer

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

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