8
$\begingroup$

The famous and ruthless explorer Wyoming Wilbert reports in the third part of his memoires that he once visited an island inhabited by jokers and truth tellers. Truth tellers always tell the truth, whereas jokers sometimes lie and sometimes tell the truth. Furthermore when a joker is killed than his body turns green, while the corpse of a dead truth teller decomposes in the ordinary fashion.

Wilbert spent several weeks in a small village with 155 inhabitants. Every village inhabitant knew exactly who the jokers were and who the truth tellers were, but Wilbert did not know the identity of a single inhabitant. However, Wilbert happened to know the exact number $j\ge2$ of jokers in the village.

On the first day, he asked every inhabitant a single yes-no question. He analyzed the answers and then killed one of the inhabitants; the corpse showed Wilbert that this guy had been a joker. On the second day, Wilbert repeated this procedure with the remaining 154 inhabitants: he asked every survivor a single yes-no question, and afterwards killed one of them. And so on, day by day, until he decided to stop.

Wyoming Wilbert reports in his book that he had designed all his questions meticulously. They guaranteed him that after several days all the jokers would be dead, while none of the truth teller had been killed.

Questions: For what values of $j\ge2$ can this story possibly be true?
What was the questioning strategy of Wyoming Wilbert?

Improve this question
$\endgroup$
3
  • $\begingroup$ Did he have to kill someone every day? For instance, if on one day all the jokers decided to tell the truth, would he still have to kill someone? $\endgroup$
    – DaaaahWhoosh
    Commented Apr 14, 2015 at 15:16
  • $\begingroup$ @DaaaahWhoosh Yes he does. You should read the "tricky part" of Taemyr's solution. It addresses this very problem. $\endgroup$
    – Allan
    Commented Apr 14, 2015 at 15:21
  • $\begingroup$ @Allan Ah, yes, I get it now. Man, that's clever. $\endgroup$
    – DaaaahWhoosh
    Commented Apr 14, 2015 at 15:26

1 Answer 1

Reset to default
3
$\begingroup$

Wilbert has a trivial strategy for the case of j=155.

Wilbert also has a strategy when j<78.

The strategy is;

  • Designate a single person as a candidate.
  • Ask villagers if the candidate is a truth teller.
  • If the first j+1 persons indicates that he is a joker at least one truth teller have stated that he is a joker and Wilbert may kill him and continue on the next day.
  • If there is disagreement among the first j+1 persons continue until j+1 persons who agree have been found. Those who disagree are all jokers, kill one of them and continue on next day. (*)
  • The tricky part is if the first j+1 all agree that the person is a truth teller. Designate the persons that have answered at this point as the first group and note that we know the candidate is a truth teller.
    • Try to use him as a rat on the remaining people as described in the previous question.
    • If this finds a joker kill him. We now have a known truth teller and can mop up as described in the previous question.
    • If this does not find a joker, we have person left that have not been asked a question, we know him to be a truth teller, and we know that there is exactly one truth teller in the first group. Pick a person in the first group, ask the truth teller if this person is a truth teller. If he is not we kill him, if he is we know that the remainder of the first group is jokers and we kill one of them. We now know all the jokers and can kill them to finish the task.

(*) If j=77 you can get in the situation that 77 persons indicate that the candidate is a truth teller and 77 indicates that he is a joker. In this case all 77 jokers must have answered with a lie, hence the candidate is a truth teller and the jokers have outed themselves.

With the exeption of j=155 Wilbert has no strategy if j>77. The strategy above is not guaranteed to suceed if j>77. This because the point marked with (*) could fail since you would not be guaranteed to find j+1 persons who agree.

Edit:

To show that no strategy can exist for j>77 just divide the jokers into two groups $j_1$ and $j_2$ such that the number of jokers in $j_1$ is equal to the number of truth tellers. If all the jokers in $j_1$ tells the truth about the jokers in $j_2$ and lies about all other inhabitants, and the jokers in $j_2$ answers randomly. This makes the situation symetrical between the thruth tellers and $j_1$ so no way to distinguish between the two groups exist.

Improve this answer
$\endgroup$
9
  • $\begingroup$ I also got the same answer as you (j < 78) or (j = 155). Another way of explaining it is that once the number of truthtellers is greater or equal to the number of jokers + 1, you can hold a "vote" to determine if someone is a truthteller or a joker since the majority of the votes will always be contributed by truthtellers. The + 1 is just in case by chance you choose a truthteller as the "candidate". $\endgroup$
    – Allan
    Commented Apr 14, 2015 at 13:07
  • $\begingroup$ Does your proof in the "Edit" preclude identifying that somebody in $j_2$ is a joker? Also what if a truth teller is asked about one of the jokers in $j_1$? That doesn't seem like it'd be symmetrical with them being asked about another truth-teller $\endgroup$
    – Ben Aaronson
    Commented Apr 14, 2015 at 14:48
  • $\begingroup$ @BenAaronson No. It's possible that strategies exist that is guaranteed kill all jokers in $j_2$ before needing to make the first unsafe kill. The jokers might have better options, especially for specific strategies. This was merely the easiest way to show that no safe strategy exist. $\endgroup$
    – Taemyr
    Commented Apr 14, 2015 at 14:52
  • $\begingroup$ @Allan Thinking of it as a vote is only good enough to get you started. It can become a dead end.(It did for me) The problem is that if the vote indicates that the candidate is a truth teller you are not guaranteed to have found any jokers. The key realization for me was that you are not after a majority, you are after a group of identical answers where the group is guaranteed to include one truth teller. $\endgroup$
    – Taemyr
    Commented Apr 14, 2015 at 14:52
  • $\begingroup$ @Taemyr I'm still not completely clear on that proof. If there was a strategy that let you safely kill all the jokers in $j_2$, you'd now also have several days' worth of information, including- possibly- questions you've asked truth-tellers about each other and $j_1$ jokers. $\endgroup$
    – Ben Aaronson
    Commented Apr 14, 2015 at 14:55

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.