IBM Ponder This #155 · March 2011

A spaceship has 100,000 bits of storage, and one of these bits is known to be faulty. You can locate the faulty bit using agents that run on any given subset of bits and return "OK" if all of the bits are good and die if they encounter the faulty bit. It takes an agent one hour to run a query, regardless of the size of the subset, but an infinite number of agents can run simultaneously. You need to find the wrong bit in two hours.

Since we must decide, in advance, how many agents to send with the spaceship, we are interested in the following questions:

A. What is the minimal number of agents needed? (Bonus question: Find a formula for the number of agents needed for n bits and t hours).

B. Suppose we want to send enough agents to be able to repeat the same task a second time with the remaining agents (i.e., those who did not die during the first invocation). How many agents are needed in that scenario?

Bonus question: Part A would require the same number of agents even if we increased the number of bits in the question by no more than X. What is this X and what is the connection between it and a recent event in IBM's history?

Update March 2nd: Different agents can access the same memory bit at the same time.

Solution

Best opened after a real attempt

To be added.