Managers and Engineers

Computer Science Level pending

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.

Your task is to identify one engineer or manager. This is because after identifying an engineer, he can tell who are the managers, or if you identify the manager, he will confess and tell who are the remaining managers.

You perform the following algorithm - maintain three sets of people: UNSEEN, STACK, and DISCARD. Initialize the process by picking one arbitrarily to be the STACK, everything else is UNSEEN. Repeat the following step until UNSEEN is empty:

  • Pick an UNSEEN person \(x\), remove it from UNSEEN.
  • Ask the top of the STACK \(y\) about \(x\).
  • If \(y\) says "manager" pop \(y\) off the stack and DISCARD both \(x\) and \(y\).
  • If \(y\) says "engineer" add \(x\) to the top of the STACK.

After UNSEEN is empty, what can we say about the top of the STACK?

Assume that there are more engineers than managers.


Problem Loading...

Note Loading...

Set Loading...