25
$\begingroup$

The famous and ruthless explorer Wyoming Wilbert reports in one of his books 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. 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 whether this guy had been a joker or a truth teller. 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 at most one truth teller had been killed.

Question: What was the questioning strategy of Wyoming Wilbert?

$\endgroup$
  • 4
    $\begingroup$ Does each one of them know who is a joker and who is a truth teller? $\endgroup$ – Akiiino Apr 6 '15 at 13:57
  • 3
    $\begingroup$ When you say Jokers sometimes lie, does this hold even if you ask an "obvious" question: ie "what's 2+2?" Are they compelled to randomly answer truth or lie? or can they opt to answer truth since they understand the question is glaringly obvious ;) (obviously if even some of them will lie to even this question, then the answer's pretty straight forward - just ask them an "obvious" question ... some will lie ... ) lather, rinse repeat. O.o $\endgroup$ – Ditto Apr 6 '15 at 14:20
  • 1
  • 18
    $\begingroup$ What is Wyoming Wilbert's motive for committing genocide? $\endgroup$ – Neil Apr 6 '15 at 22:39
  • 8
    $\begingroup$ @Neil: Science, what else? $\endgroup$ – Nova Apr 7 '15 at 6:06

11 Answers 11

26
$\begingroup$

This is exactly question 7 of the 2015 Tournament of Towns.

A Solution:

Round the inhabitants into a circle, with one volunteer sacrifice in the center. Ask everyone in the circle about the centerpiece, is he a joker or is he a truth teller? We have two possible outcomes: (1) everyone says the man in the center is a joker, or (2) at least one person vouches for him.

(1) Since everyone thinks he is a joker, it is reasonable to kill him and see what color he turns. If he was a joker, no matter, we now have less people and we haven't killed any truth tellers, so we may continue by induction. If he was a truth teller, then we deduce that every single other village inhabitant lied and are thus jokers, so we may proceed to kill them all without asking any more questions.

(2) Since not everyone thinks that the man in the center is a joker, we don't want to risk killing him. Instead, we will kill someone who claimed that he is a truth teller. Either our victim was a joker and we may continue by induction, or our victim was a truth teller and it is a shame that we killed him, but we win anyways: he gave us the useful information that the center is also a truth teller. This means that we can use our now known truth teller as a rat on the rest of the village.

RAT: To use our truth teller as a rat, we line up the inhabitants with our truth teller at the back, and ask him what he thinks of the villager directly in front of him. Our rat will either tell us that the one in front of him is no good (we kill him and continue by induction) or that the one in front of him is good, then we move our old rat to a safe zone and continue by induction with our new rat (base case is trivial).

$\endgroup$
  • 1
    $\begingroup$ The wording is not very clear in the second paragraph. What do you mean by "If he was innocent ..." ? $\endgroup$ – AJMansfield Apr 6 '15 at 16:56
  • 9
    $\begingroup$ This is the correct answer, but I would suggest clarifying that "condemned" means "EVERY person said he was a joker". And also explain how you would use your "rat". Since you can only ask each villager one question per day, you would need to ask the rat "Is villager 1 a joker", then ask villager 1 "Is villager 2" a joker, etc. until someone says "yes". Or until everyone says "no", in which case your job is done. $\endgroup$ – Taylor Brandstetter Apr 6 '15 at 17:59
  • $\begingroup$ @AJMansfield, By innocent I mean truth teller.. I guess jokers are innocent too though :/. Taylor Brandstetter, you are correct. $\endgroup$ – Ben Frankel Apr 6 '15 at 18:54
  • $\begingroup$ this is horrible to read for non english speakers $\endgroup$ – Vajura Apr 7 '15 at 12:50
  • $\begingroup$ @Vajura, Sorry :/. You can look at Allan's solution, I think it may be easier to read. $\endgroup$ – Ben Frankel Apr 7 '15 at 12:54
12
$\begingroup$

NOTE: Although some of these answers are correct, some of them do not obey the rule that you can only ask each villager a yes-or-no question and that you can only ask them one question per day. Also in each day, you must kill one person.

I'm not sure if stage 1 of the method described here is the same as what Ben Frankel is describing; since he doesn't explore the case when the volunteer is actually a joker.


STAGE 1: Finding a truthteller

First, take a random villager and let's call them the pivot.

Ask every single villager (except for the pivot) if the pivot is a truthteller and kill the first person who answers yes to the question (claiming that the pivot is a truthteller).

CASE 1: The pivot is actually a truthteller.

Eventually you will reach a truthteller who you kill and this will confirm the fact that the pivot is a truthteller.

CASE 2: The pivot is actually a Joker.

This means that you will only kill jokers and eventually you will reach a stage where all the villagers answer no (claiming that the pivot is not a truthteller). In this case, kill the pivot, and pick a new pivot only if the pivot was not a truthteller (see below).

SPECIAL CASE: There is only one truthteller.

In an event where there is only one truthteller, eventually you will pick the truthteller as a pivot and you will also eventually reach the stage where all the villagers answer no to your question (claiming that the pivot is not a truthteller). After killing the pivot, you will then know that everyone had been lying and thus you can now proceed with the massacre. (thank you to Prem for pointing this out)


STAGE 2: Using the truthteller

Now that you've found a truthteller, you can use them as a starting point to kill jokers. You now need to use the truthteller and ask them if another unknown person is a truthteller. enter image description here

CASE 1: The truthteller says no (meaning the unknown is a Joker)

Kill the Joker and you are done for the day. enter image description here

CASE 2: The truthteller says yes (meaning the unknown is a truthteller).

You now have to ask the new truthteller if another unknown is a truthteller. enter image description here


Eventally, you will reach a case where all the villagers answer yes which implies that all the villagers are truthtellers.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Nice. One point is left out : In stage 1 case 2, when all villagers say "No", and we kill the pivot : If pivot is a truthteller, then all remaining villagers are Jokers, so no need for more pivots. If pivot was a Joker, then select another pivot. $\endgroup$ – Prem Apr 7 '15 at 2:51
  • 2
    $\begingroup$ Yes, you are absolutely right. If everyone says that the pivot is a joker but you find out it's not, then they all must be lying. This would imply that of all the villagers, only one person is a truthteller (shame you had to kill them). $\endgroup$ – Allan Apr 7 '15 at 3:16
3
$\begingroup$

Quite simple: He asked to one inhabitant to tell him which ones of the inhabitants were jokers and after that killed the inhabitant. If the inhabitant was a joker, Wyoming Wilbert repeated the process the next day. Now, if the inhabitant was a truth teller, he discovered the identity of all the jokers, making easy to know which ones he had to kill next.

Plus: If he wanted to speed up the process, questioning also to all of the inhabitants who was a truth teller would help, so he would know someone who would answer the truth before dying (if the inhabitants confirmed in unanimity).

Obs: Still improving my english skills, sorry if I wrote something wrong.

$\endgroup$
  • 1
    $\begingroup$ The question says that "He asked every inhabitant a single question", but this solution requires asking many questions to a single inhabitant, so this solution will not work. $\endgroup$ – Prem Apr 6 '15 at 18:11
  • $\begingroup$ @Yamikuronue, "he asked every inhabitant a single yes-no question" $\endgroup$ – Ben Frankel Apr 6 '15 at 19:29
  • $\begingroup$ @BenFrankel Oh, my bad $\endgroup$ – Yamikuronue Apr 6 '15 at 19:30
  • $\begingroup$ @Prem, you are right, I've not paid attention to that part of the puzzle. Thanks. $\endgroup$ – Cesar Martini Apr 6 '15 at 23:38
3
$\begingroup$

Edit: I now believe Ben Frankel's answer is the correct one. As long as the TT you kill has fingered someone else as a TT, you know have a known TT with which you can identify all Jokers.

I'm inclined to say that there's no correct answer.

All the given answers fail in the case where every Joker behaves as if they were at Truth Teller on the first and second nights. Note that this is not the same as telling the truth: A Joker behaving as a Truth Teller, when asked "are you a truth teller?" will respond "Yes."

Wyoming Wilbert will learn no information that distinguishes between Truth Tellers and Jokers, and will not be able to reliably select a Joker to kill on the second night, thereby violating the clause that at most one truth teller had been killed.

$\endgroup$
  • 1
    $\begingroup$ But if on the first night you kill a truth teller, you gain some information, in particular, the information that the victim had answered your question truthfully. If you asked him something useful about the truth teller/joker state of some other villager, then you have indeed gained information. $\endgroup$ – Ben Frankel Apr 6 '15 at 19:31
3
$\begingroup$

I would ask:

Am I going to kill you today?

Unknown says: NO. Then you kill him. (joker 100%)

Unknown says: YES. Left him alive. (and tomorrow kill him without asking) joker!

A truth teller cannot respond. Because if you don't kill him, he is a joker.

Senseless I know, but it would work!

$\endgroup$
  • 1
    $\begingroup$ So.. If he's not a joker, make him a joker. I know this isn't the "Correct" answer, but it's not "wrong". Well maybe morally wrong, but not logically wrong. Have an upvote. $\endgroup$ – Andrew T Apr 7 '15 at 17:20
  • $\begingroup$ Seems like a paradox. So this is more of a "yes-no-answerless" question. $\endgroup$ – Allan Apr 7 '15 at 22:51
  • 1
    $\begingroup$ I know this is not the "correct answer" but this one fits the problem. i just wanted to show an alternative answer "stupid but valid". $\endgroup$ – A Joker Apr 8 '15 at 15:00
2
$\begingroup$

Every day, you ask each of the town inhabitants:

Are there any Jokers still alive on this island?

If they reply with Yes, then you let them live.

If they reply with No, you kill them.

Rinse and repeat this process each day.

You know there are no more Jokers once the person you killed doesn't go green.

Thus, all Jokers are dead, and at most one truth teller.

$\endgroup$
0
$\begingroup$

This can be done without the villagers having any prior knowledge of each other.

Each day, ask each villager the following question:

Have I killed more than one truth teller?

Kill anyone that answers "Yes".

$\endgroup$
  • $\begingroup$ And if they all answer "No"? $\endgroup$ – Ben Frankel Apr 6 '15 at 14:30
  • $\begingroup$ Ask them again tomorrow. $\endgroup$ – Ian MacDonald Apr 6 '15 at 14:30
  • 1
    $\begingroup$ So they all answer "No", you kill someone randomly and it turns out he was a truth teller. The next day, you ask everyone and they all answer "No". You kill someone randomly and it turns out he was a truth teller. You lose $\endgroup$ – Ben Frankel Apr 6 '15 at 14:32
  • $\begingroup$ Why would I randomly kill someone? $\endgroup$ – Ian MacDonald Apr 6 '15 at 14:32
  • 3
    $\begingroup$ If you don't kill anyone then you haven't made any progress. The process could be infinite, why would anyone say "Yes" and give themselves away? "They guaranteed him that after several days all the jokers would be dead", ie, the process must be finite. $\endgroup$ – Ben Frankel Apr 6 '15 at 14:34
0
$\begingroup$

When asked if he is a joker, any truth-sayer will say "no." When asked if he is a joker, any joker will also say "no" - because he is lying. That means that when asked, everyone in the village will deny they are a joker.

Then ask everyone in the village the following question: "If I ask you if you are a joker will you say "no"? "

A truth sayer will say "yes". A joker will say "no" - because he's lying.

And that's how you find all the jokers.

$\endgroup$
  • 4
    $\begingroup$ Not necessarily. The jokers can tell the truth, they just do not always tell the truth $\endgroup$ – Brian Robbins Apr 6 '15 at 18:22
0
$\begingroup$

Trying something new; Not sure if this goes against the rule of the question:

Ask with the phase: "I am gonna kill all truth tellers, are you a joker?" by assuming all inhabitants wanted to survive. Truth teller have to say no, while all joker will always lying with yes, thus killing them afterward.

$\endgroup$
  • $\begingroup$ If that works then the riddle becomes trivial. You could ask something along the lines of, "Is Steve a joker? If I kill him and find out that you lied to me, I'm going to kill you." And that would basically allow you to use any person, joker or truth teller, as a known truth teller (if he says no you kill him and either he was telling the truth and you win or he was lying and you don't care) $\endgroup$ – Ben Frankel Apr 6 '15 at 19:36
  • $\begingroup$ I see, I was trying to save that one bad luck truth teller Brian =D $\endgroup$ – Alex Apr 6 '15 at 19:42
  • $\begingroup$ Maybe it's possible to put together an interesting riddle with truth tellers and jokers who answer only based on what will make them survive as long as possible, but I think such a riddle would have too many loopholes. $\endgroup$ – Ben Frankel Apr 6 '15 at 20:10
0
$\begingroup$

Not a single truth teller needs to die.

Ask, "Should I kill you?"

Now, anybody who is suicidal doesn't need this prompt and would have already committed suicide. Therefore, no truth teller will answer, "Yes", that they wish to die, but some jokers will. Therefore, by attrition, by repeatedly asking the question, only jokers will eventually all be killed, while not a single truth teller will be harmed.

$\endgroup$
  • $\begingroup$ No workee. Jokers might mask their identity indefinitely. $\endgroup$ – Joshua Apr 7 '15 at 15:51
  • $\begingroup$ @Joshua That would not make them jokers. They would be predictable liars. I am assuming, of course, that jokers are randomly foolish. I assume this because they are called jokers, as in fools, not comedians or liars. $\endgroup$ – Jason Feldes Apr 8 '15 at 12:40
0
$\begingroup$

Ask "Are you a joker that is telling the truth?" The jokers have to answer "yes," regardless of whether they are lying or telling the truth; the truth tellers have to answer "no."

$\endgroup$
  • $\begingroup$ Why do the jokers have to say yes? $\endgroup$ – Allan Apr 7 '15 at 22:44
  • $\begingroup$ Because if they decide to lie, they have to say something other than no, as no would be telling the truth $\endgroup$ – Andrew Smith Apr 8 '15 at 4:12
  • $\begingroup$ If a joker says yes, then they are indeed telling the truth. The question states that jokers can sometimes tell the truth and sometimes lie. $\endgroup$ – Allan Apr 8 '15 at 8:54
  • $\begingroup$ Yes, and if they are lying, the answer "Yes" to the question is a lie. We don't have to determine they are lying, only that they are jokers. $\endgroup$ – Andrew Smith Apr 8 '15 at 8:55
  • $\begingroup$ Answering no is also a lie though. $\endgroup$ – Allan Apr 8 '15 at 8:57

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.