# Knights and Knaves in the Wild West

Late at night at a bar in the Wild West only two cowboys from out of town are left, playing poker with the barkeeper. One of them cheats, so another throws over the table and they have a fistfight (the barkeeper wisely having confiscated the guns), ruining the bar. Awakened by this, the neighbors call for the sheriff to put someone behind bars.

The sheriff knows that white hats always tell the truth, black hats always lie, and barkeepers answer like the one asked right before him would. Unfortunately, the hats were knocked off during the fight. Also, neither the sheriff (nor the neighbors, who went back to sleep already) know which one is the barkeep because he's new in town, shaved this morning for the first time in years, it's always quite dark in the bar and whatever.

What questions should the sheriff ask to find out who started the fight?

• a) Do they have to be yes-no questions? b) What happens if the first question is addressed to the barkeeper - does he answer randomly or what? Apr 12 '15 at 13:46
• (a) Yes, it should be yes-no-questions. What does this exclude? head-exploding or open questions? (b) Yes, if the barkeeper is addressed first his answer should be considered random. Apr 12 '15 at 14:39
• This is the hardest logic puzzle ever except that you know the meanings of yes and no and the bartender is specified to follow the previous instead of answering randomly. You can follow that solution. Apr 12 '15 at 14:49
• c) Do we know that one cowboy was black-hat and the other white-hat, or could they both be the same? d) Do we know the barkeeper wasn't the one to start the fight? Apr 12 '15 at 14:57
• Could you explain what is wrong with a standard question "What would you answer if I ask you whether this person started the fight?"? Doesn't matter who it is asked - knight or knave - the answer would be the same, since barkeeper chooses to "play" one of them he will answer the same too. Apr 12 '15 at 19:39

## The original question

Ask each person if they are the barkeep. The aim of this question is not to identify the barkeep but to find the white hat or the black hat.

If only one person answers 'no' then that person is the white hat (the black hat will always claim to be the barkeep, the barkeep in this case has answered truthfully).

If two people answer 'no' then the one person who answered yes must be the black hat. (the barkeep in this case has answered has lied).

Now that one of the cowboys has been identified that cowboy can be interrogated to reveal who started the fight, (remembering to assume to opposite if it was the black hat who was initially identified), and if you desire the identities of the other two.

## Various variations

If there happened to be more than two cowboys and/or more than one barkeep the procedure is roughly the same and should work as long as there is at least one white hat.

If only one answers 'no' initially they are the only white hat and the problem is solved. (Just ask him who started the fight.)

If more than one answers 'no' then you may have more than one white hat or a white hat(s) and a confused barkeep. Ask one of them if they are the barkeep again.

If they now answer 'yes' that is the barkeep (and you must have questioned a black hat in the last round of question.)

If not ask each of those white hat/bar keep candidates if the barkeep has lied so far. If any answer 'yes' then you have just found a white hat amongst this subgroup, again the problem is solved. If no one answers 'yes' to this question the subgroup contains only white hats and your problems are over.

If it is possible that there are no white hats present then you have a more difficult problem. It is still possible to work out who is/are the barkeep(s) (or if you have a room full black hats) but it will take repeated rounds of questioning, changing the order and questions.

NOTE: I've revised this answer so that it can work with any number of white hats and black hats. The only requirement is that there is only one bartender (and of course the rules stated in the question still apply here). This method will also work if more than one person started the fight since this method involves determining the identity of every single person.

## Stage 1: Finding the bartender

First, put the 3 unknowns into a line. We then question each person starting from 1 to 3 and ask them the following question.
Are you a black hat?

Both the white hats and black hats will always answer no. claiming that they are not black hats, (highlighted in red in the chart below). On the other hand, the bartender will sometimes answer yes and sometimes answer no; depending on if the last person asked was a white hat or black hat.

If we ask the question and everyone says no, then we simply ask again in a different order. Eventually, we will fall on the case where the bartender answers yes, and thus we have found the bartender.

NOTE: There is a 50% chance that the bartender will say yes as shown in the truth table.

## Stage 2: Determining the identites of all the people

Once we know who the bartender is, we can use the fact that the bartender will always answer the same way as the last person who was asked. To determine the identity of an unknown person we simply ask them if they are a black hat, then we proceed to ask the bartender if the bartender themself is a black hat.

We have two cases as illustrated in the table below.

If the last person asked was a black hat, the bartender will also lie and say yes, I am a black hat (which we know is a lie). However if the last person asked was a white hat, then the bartender will answer the truth and say no, I am not a black hat (which we know is true).

Based on whether the bartender answers yes or no, we can determine if the previous person asked was a black hat or a white hat. Using this method, we can then go on to figure out the identities of all the other people (or until we find a white hat for the purposes of this riddle).

Once we've found a white hat, we can ask them who started the fight and thus figure out who needs to be put behind bars.

Or if you want to be real picky and follow the rules all the way through (yes-or-no questions only), you can use the white hat as a pivot to determine if someone had started the fight since they will always tell the truth (i.e. ask the white hat if "this person" started the fight and keep doing this for every person).

• "it should be yes-no-questions" Apr 12 '15 at 18:31
• Ah alright, I will change my answer then. Apr 12 '15 at 18:32
• But what about the innkeeper? There are three unknowns, not two. Apr 12 '15 at 19:03
• Where in the question does it ask us to figure out who the innkeeper is? The question just asks us to figure out who started the fight. The innkeeper was just used as part of the storyline, we don't actually care about him. Apr 12 '15 at 19:05
• In this comment, the OP makes clear that it might have been the innkeeper who starts the fight. Apr 12 '15 at 19:13

If the sheriff asks just one person all the questions, that person will always answer consistently. The cowboys certainly will. The barkeep will start randomly with truth or lie, but then will keep telling the truth or keep lying.

The sheriff selects any one of the three people as witness, then points to each person in turn and asks the selected witness, "Did this person start the fight?"

The witness would give one answer (Y/N) when you point to the culprit, and the opposite answer (N/Y) when you point to the other two. Arrest whoever the witness answers differently about. E.g. YNY: arrest B; or YNN: arrest A.

The sheriff asks 3 simple questions in total.

• What if the barkeeper is the person asked and the real answer to your first question is "no"? Then he would answer Y/N randomly to the first question, and Y,N in some order to the second and third, and you can't deduce which is the culprit. Apr 13 '15 at 0:07
• Actually, no. "Barkeepers answer like the one asked right before him would", and randomly to the first question, so he must answer randomly to all questions if you keep asking him. Apr 13 '15 at 0:08
• @randal'thor The assumption is that the barkeep last spoke with a cowboy - the story preamble has just the barkeep and two cowboys remaining by the time of the tussle :). I originally had a preliminary set of 3 questions to exclude the barkeep: the sheriff can use these if need be. cont'd Apr 13 '15 at 0:13
• @randal'thor cont'd. The two cowboys always give opposite answers. If the sheriff wants to exclude the barkeep, label the 3 people $A,B,C$. Ask each of them in that order, "Did $A$ start the fight?" If $A=B$, the barkeep is either $A$ (answering randomly) or $B$. If $B=C$, the barkeep is $C$. Otherwise, we have $A \neq B$ and $B \neq C$ and the barkeep is $A$. Select any cowboy for the 3 questions in my original answer. Total 6 questions now, but all are still simple questions, none self-referential or of the "would X say Y" type. Apr 13 '15 at 0:18

If you only care about who started the fight, it can be done in

three questions.

If you want to keep the questions simple, it can be done in

four.

First:

Consider the question "Did the white-hatted cowboy start the fight?" The cowboy who started the fight answers yes; the cowboy who didn't answers no; the bartender gives the same answer as the person before him.
Call them Tom, Dick, Harry.

Method using only simple questions: