On one of the Islands of Knights and Knaves you land for the purposes of an anthropological survey. The Island has Knights who always tell the truth ( if they know enough information regarding a question put to them) and Knaves who always lie ( also if they know enough relevent info.) ( Of course a Knight or Knave could respond with a respectively true of false statement even if they didn't know enough relevent info.) Also on the Island are the Tax-collectors , inhabitants who sometimes lie and sometimes tell the truth. The thing is these tax-collectors are very good at hiding what 'type' of inhabitant they are. For example if you ask directly a person whom you don't know is a tax-collector 'What is (2+2)?', If he answers 4 and you ask him again in one hour he won't say 5. The tax collectors have great memories and even if he forgets a previous response he might say, 'What did I say before'? You're wondering if there is one sure fire yes-or-no question that if a person responds you can tell what 'type' they are. Is there such a question?
3 Answers
A simple counter example would be the horrible island of all tax-collectors, who all mimic knights perfectly - always tell the truth about everything, except pretending that everyone on the island is a knight.
You could have a lifetime of questions on this island and could never find any difference to an island full of actual knights.
Intuitive Answer
Assuming "sometimes lies and sometimes tells the truth" means that a tax collector will lie for at least one question and tell the truth for at least one question, then we can have the following two tax collector collections:
- Tax collectors of type #1 will give the same answer a Knight gives except for "does 1=1?", where they'll say "no".
- Tax collectors of type #2 will tell the same answer a Knight gives except for "does 2=2?", where they'll say "no".
The first question cannot distinguish #1 from Knaves or #2 from Knights. The second question cannot distinguish #2 from Knaves or #1 from Knights. For any other question, the tax collectors are functionally identical to Knights and cannot be distinguished. So the answer is no, no single question is enough to distinguish Knights and Knaves from Tax Collectors.
Note that using "answers like a Knight" instead of "tells the truth" means we don't have to think about tricky meta questions ("what would you say if I asked you 'does 1=1 AND is your answer to 2=2 false'?"), because the tax collector will treat the entire thing as if it were a Knight, not break it down and answer each piece like a tax collector.
Math Answer
There are three possibilities: Knight, Knave, tax collector. There are two possibilities for an answer: yes, no. So for any given question, one answer must map to Knight/Knave and the other must map to Knight or collector/Knave or collector. So you can't distinguish them with just one question.
-
$\begingroup$ Well put. If a tax collector is indistiguishable from another type of person, there is no way to establish a difference between them. Maybe you learn what they are not, but it is not enough to infer who they are with a single question. $\endgroup$– NeilSep 22, 2014 at 13:37
-
1$\begingroup$ There are at least 3 possible answers ; yes , no and some response equivalent to maybe. Just because you ask a yes or no question you can't stop the inhabitant from saying 'maybe' or 'I don't know' or 'that's a good question'. I said in the question, you want to ask a 'yes or no' question and from their response ( whatever it is) you can tell what type they are. I noticed hovercouch made an excellent point that a Knight wouldn't say 'maybe', though I think a Knave could say 'maybe' (if is not the truth). $\endgroup$ Sep 23, 2014 at 4:33
From the formulation I would conclude that a tax-collector can answer whatever he finds reasonable, using any unknown algorithm to generate answer. This includes random generator algorithms for questions which are asked a first time (and the next time, he will repeat the answer).
In this case, it is quite obvious that the answer is no. There is no useful information that you can extract from a tax-collector answer independently of what you are asking. This includes information about the type of the asked person.
(Though, if you know somebody who is not tax-collector you can ask about a person you are interested in "what would you answer if I ask you what type is this person?".)
-
$\begingroup$ Say an inhabitant you don't know named Mr. E is you're next interviewee. You might ask if a tax collector was here also ( and Mr. E knows this person) and you ask them both this 'special' question ( if it exists) would they answer in a similar way? If Mr. E is a Knave and the special question 'works' he would say Yes. If Mr. E is a Knight he would No. If Mr.E is a tax collector he might say yes but this would show he is not a Knight. Since he wants to hide his type he might not say yes. Similarly he might not say no. He might say 'maybe'. $\endgroup$ Sep 21, 2014 at 23:16
-
$\begingroup$ @user128932, I don't understand your point.. $\endgroup$– klm123Sep 21, 2014 at 23:48
-
1$\begingroup$ @user128932 if Mr. E says 'maybe' you immediately know he's a tax collector, since Knights and Knaves would never say "maybe". $\endgroup$ Sep 22, 2014 at 4:32
-
$\begingroup$ If you meet Mr.E and you as ask him if he had a friend here who was the same 'type' as himself and he asked the 'special question' ( if it exits) to his friend would his friend possibly say 'Maybe I'm not the same type as you Mr.E'? If Mr.E is a Knight he would say 'no'. If Mr.E is a knave he would say yes. If the person is a tax-collector he would know a tax-collector might say yes to the question or he might not so in this case a true answer might be 'maybe' if he was speaking the truth. So this is a partial answer to whether there is a question that can tell the 3 'types'. $\endgroup$ Sep 23, 2014 at 5:14
-
2$\begingroup$ @user128932 I think we, the puzzler answerers, might be misunderstanding the question. Tax collectors can follow a strategy, right? If so, that doesn't work, because a tax collector can have the strategy "give the same answer a knight would give" and say no. $\endgroup$ Sep 23, 2014 at 15:15