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.
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?
FBI包圍了Norne公司總部。大樓裏有 n 個人，其中有工程師，也有經理。所有電腦文件都被刪除了，所有文檔讓經理銷毀了。FBI 調查組面臨的問題是，如何將這些人分成兩組，經理和工程師。然後，扣留所有經理，釋放所有工程師。這 n 個人都知道彼此認識。假定i，j 是這n個人中的任意兩個人，調查組只能問 i，“j 是工程師還是經理？”這樣的問題。
工程師總是說真話，經理可能不會說真話。事實上，經理都是鬼才，總是想混淆視聽。
問題：
1、假如半數以上的人是工程師，你能否給FBI調查組提供一個策略，用最多 n-1 個問題找出一位工程師？
2、如果半數以上的人是經理，用任意數目個問題，能否找出一個工程師。
3、找出一個工程師，當然就可以將所有人都分辨出來。是否能用更少的問題確定每個人的身份呢？
Solution
Part 1: A correct, optimal, and elegant solution was submitted by Chris Peikert, Grant Wang, and Abhi Shelat of MIT. A number of others submitted partial solutions.
Here's an n-1 query solution to part 1. 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 element 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 it says "engineer" add x to the top of the STACK.
After all elements have been processed in this way (n-1 comparisons), the top of the stack must be an engineer.
Why does this work? First observe that whenever we discard a pair, at least one of them is a manager. So among the rest of them (STACK and UNSEEN) a majority must still be engineers. So at the end, when UNSEEN is empty, there must be an engineer in the stack, therefore the top of the stack must be an engineer.
This can be improved to n-2 simply by stopping one earlier. When there's one UNSEEN left, if the stack is empty, that UNSEEN one is an engineer. Otherwise, the top of the stack must be an engineer.
If is n is even and n>=4, as a first step we can just throw out one person, and appy this algorithm to the remaining n-1 obtaining n-3 comparisons. This gives the optimal algorithm.
This is optimal. The proof appears in the solution of homework assignment 7 of Steven Rudich's course 15-251 taught at CMU in the spring semester of 2002. See Solution 7.
Part 2: If half or more of the people are managers, then the problem cannot be solved. The managers can ensure this simply by always lying. Now there's way to separate the two sets of people. Each one simply claims the others are Managers.
Part 3: I don't know any better solution than to simply using the solution to Part 1 to identify everybody.
解答：
1、n-1 個詢問解決第一個問題：
維護三個集合，UNSEEN, STACK，DISCARD。初始時，隨便選一個人放到 STACK，其餘的都是 UNSEEN。重復下面的步驟，直到 UNSEEN 空了。
挑一個 UNSEEN 中的人 x ，從 UNSEEN 中移走他。詢問 STACK 頂上的人——不妨稱他為y：“x 是工程師還是經理？”，
如果y說是“經理”，將 y 剔出 STACK，x 和 y 都送到 DISCARD。如果 y 說是“工程師”，將 x 放到 STACK 頂上。
所有人都經過這樣的處理之後，STACK頂上的一定是個工程師。
這方法爲什麽可行？一眼可以看出，送到 DISCARD 的每一對中至少有一個經理，所以 STACK 和 UNSEEN 中還是工程師佔多數。最終，儅 UNSEEN 為空時，STACK 裏一定有一個工程師，因此 STACCK 頂上的一定是工程師。（可以反過來想，如果 STACCK 頂上的不是工程師，則 STACK 中所有人都將是經理，這不符合工程師過半的條件。）
其實儅 UNSEEN 中還剩一個人的時候，就已經可以判斷，如果 STACK 是空的，則這個人就是工程師，否則 STACK 頂上的人是工程師。
如果 n 是偶數且 n>=4 ，第一個步，可以提出一個人，對 n-1 個人用上面的方法，因爲這 n-1 個人中工程師還是佔多數。這樣可以少問一個問題。
其實，詢問的過程中，如果 STACK 空了，可以隨便挑一個 UNSEEN 的人到 STACK 上，這樣就又可以少問題。這和問人的順序有關，運氣好， n/2 個問題就可以了。