March 2011
<<February March April>>
Using n agents in t hours, we can discover a faulty bit from a set of (t+1)^n bits.
We prove that using induction on t. The base (t=0) is trivial. For larger t's, we write the bit addresses in base t+1 and give the i-th agent to test the numbers whose i-th digit is t. After an hour, we are left with k living agents, n-k known digits, and k digits with only t possible values, which suits the induction.
If we have two hours to find the faulty bit (t=2), we need 11 (ceil(log_3 100,000)) agents to solve part A. The general formula is that n agents in t hours can find a faulty bit out of (t+1)^n bits. 11 agents are sufficient to solve for 3^11 bit, which is 77,147 more than 100,000. 77,147 is the dollar sum racked up by IBM's Watson while winning Jeopardy! last month.
Applying the strategy above (giving the i-th agent to check, in the first hour, the bits whose address contains a "2" in the i-th ternary digit and, in the second hour, giving the i-th agent to check the bits whose address contains a "1" in the i-th ternary digit) solves past A with 11 agents, but the problem is that in some cases, we might lose all 11 agents.
If we use 16 agents we can guarantee not loosing more than 5 of them in the first hour by omitting all the 16 bits numbers having less than 11 "0"s and renumbering the rest 173,889 (which is more than 100,000).
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com