Engineers vs Managers

[BMAD]

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 iif 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.

1. 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?
2. Is this possible in any number of questions if half the people are managers?
3. Once an engineer is found, he/she can classify everybody else. Is there a way to classify everybody in fewer questions?

[plasmid]

Answer to question 1
 

Spoiler

Starting at person number m=2, ask person m whether person (m-1) is an engineer.

a) If m says (m-1) is an engineer, consider m to be vouching for the engineerhood of (m-1). Increment m by one and continue the process, so for example the second question would be to ask person #3 whether person #2 is an engineer.

b) If m says (m-1) is not an engineer, then you know for sure that m and (m-1) can't both be engineers, so throw out both m and (m-1). By throwing them both out, you will have reduced the number of managers by at least one, and you would have reduced the number of engineers by no more than one, so the engineers will still be in the majority. After you've thrown those two out, when you increment m by one and ask the next person whether the preceding person is an engineer, since person (m-1) has been thrown out, ask them whether the person with the largest number less than m that's still remaining is an engineer. If everyone with a number smaller than m has been thrown out (such as if you start off by asking person #2 whether person #1 is an engineer and they say no so you throw them both out and proceed to m=3) then skip that person and increment m by one again and ask them whether the preceding person is an engineer.

At the end of the process, you will end up with the remaining people forming a chain where each remaining person vouched for the person with the number just smaller than theirs. You know that there cannot be a manager that is immediately followed by an engineer, or else the engineer would have ratted out the manager and you wouldn't have a chain of people vouching for each other. A manager could be within the group, but only if they're followed by another manager so they wouldn't be called out. So if there are any managers, they must occupy consecutive spots at the end of the queue. Since there are still a majority of engineers, you know that the entire first half of the remaining people must be engineers.

 

[CaptainEd]

#2: seems like plasmid's approach can solve this, too.

Spoiler

The only glitch I see is that in some configurations, ALL pairs might be removed. In that case, make two queues, placing the first member of each pair in queue 1, and the second member in queue 2. Then concatenate queue1 followed by queue2, and perform plasmid's method again. If they were all alternating in the original pass, they will be more homogeneous in the second pass, and they won't ALL be removed. 

 

[plasmid]

Question #2

Spoiler

 

In general, consider a group with an equal number of engineers and managers. The engineers will, of course, always act as if the engineers are engineers and the managers are managers. If the managers always act as if the managers are engineers and the engineers are managers, I suspect you would have a system with two groups that behave symmetrically with respect to each other and thereby with no way to differentiate the two groups.

For the specific case of applying the method for question #1 to case #2: I think the queues will always end up emptied if the managers always play correctly. Any time a manager is preceded by an engineer, he'll incriminate the engineer to get them both thrown out. If there are a string of consecutive managers (not at the beginning of the queue), the first one will incriminate the engineer immediately ahead of him, so once those two are out of the queue the next manager will be asked about the person who was ahead of the engineer that just got removed. So a string of multiple managers can remove a string of multiple engineers and vice-versa.

 

 

[CaptainEd]

I'm convinced, plasmid!