XRDS: Crossroads

MANAGERS AND ENGINEERS (WINTER 2020)

Puzzle:

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?

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.

http://www.cs.cmu.edu/puzzle/solution1.html

(SOURCE: The Puzzle Toad)

THE MAGIC MONEY MACHINE (FALL 2020)

Puzzle:

The wizards on Wall Street are up to it again. The Silverbags investment bank has invented the following machine. The machine consists of six boxes numbered 1 to 6. When you first get the machine, it contains six tokens, one in each box. You have two buttons A and B on the machine and you can press them as many times as you like and in any order.

Button A: Choose a number i from 1 to 5 and then take one token from box i and magically two tokens will be added to box i + 1.

Button B: Choose a number i from 1 to 4 and then take one token from box i and then the contents of boxes i + 1 and i + 2 will be interchanged.

The machine sells for one trillion dollars. The contract says you can take the machine back to the bank at any time and then the bank will give you one dollar for each token in the machine. Is the machine worth buying?