The FBI has surrounded the headquarters of the Norne corporation. There
are n people in the building. Each person is either an engineer
or a manager. All computer files have been deleted, and all documents
have been shredded by the managers. The problem confronting the FBI interrogation
team is to separate the people into these two classes, so that all the
managers can be locked up and all the engineers can be freed. Each of
the n people knows the status of all the others. The interrogation
consists entirely of asking person i if person j is
an engineer or a manager. The engineers always tell the truth. What makes
it hard is that the managers may not tell the truth. In fact, the managers
are evil geniuses who are conspiring to confuse the interrogators.
- Under the assumption that more than half of the people are engineers, can you find a strategy for the FBI to find one engineer with at most n-1 questions?
- Is this possible in any number of questions if half the people are managers?
- Once an engineer is found, he/she can classify everybody else. Is there a way to classify everybody in fewer questions?
2 comments:
Stupid FBI... just give them a task that a manager can't accomplish (i.e. using a log table), and you get your engineer ;-)
But to solve the riddle: If an engineer always tells the truth and a manager tells what he believes suits him best (i.e. prevent the FBI from finding a real engineer), you just pick one random person and ask everyone what he is (n-1 questions).
If the guy is an engineer, all the managers will lie so that you don't use this guy to identify them. If the guy is a manager, all the other managers will pretend that this guy is an engineer, in order to make you pick him and rely on his words, so again they will all lie.
If more than half of the people are engineers, than wither half or more than half of the answers about the guy will be true. So the answer which you get most often is correct. If the guy turns out to be a manager, just pick one witness that told you the truth, and there you have your engineer.
When n is even, at least (1+n/2) engineers are present. So you get at least n/2 correct answers (if you picked an engineer as your sample guy, and then you have n/2 -1 wrong answers).
When n is odd, you have at least 0.5 +n/2 engineers. If your sample guy is a manager, you get (0.5 +n/2) correct answers and (n/2 -1.5) lies. If your sample guy is an engineer, you get the same number of right and wrong answers, and because you knew that there were more engineers than managers, you know that you actually picked an engineer.
If exactly n/2 are managers (and you know this), you again pick one sample guy and ask everybody about him. No matter what he really is, you will get (n/2 - 1) answers that he is an engineer and n/2 answers that he's a manager. Now divide the people from which you got the answers in two groups: the group which said "engineer" (plus your sample guy, because he's certainly the same type as them) and the group which said "manager". Now you are sure that one group consists of truth-tellers (i.e. engineers) and the other group consists of liars (i.e. managers).
So you have successfully separated the managers from the engineers - just you still don't know which group is which.
In order to find that out, you need to be allowed to ask a different kind of question.
Post a Comment