Ponder This Challenge - March 2011 - Locating faulty bits

Ponder This Challenge:

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.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  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).

Solvers

• Michael Brand (03/01/2011 02:33 PM EDT)
• Joseph DeVincentis (03/01/2011 02:39 PM EDT)
• János Kramár (03/01/2011 03:42 PM EDT)
• Chuck Carroll (03/01/2011 04:00 PM EDT)
• Alan Murray (03/02/2011 02:36 AM EDT)
• James Dow Allen (03/02/2011 06:41 AM EDT)
• Austin Shapiro (03/02/2011 04:52 PM EDT)
• Alan Curry (03/03/2011 03:16 AM EDT)
• Aviv Nisgav (03/03/2011 04:07 AM EDT)
• Dmitry Litvinenko (03/03/2011 06:00 AM EDT)
• Stephen Herbert (03/04/2011 12:42 PM EDT)
• David Blackston (03/04/2011 02:16 PM EDT)
• Sangxia Huang (03/04/2011 03:33 PM EDT)
• Nemo Publius (03/04/2011 03:34 PM EDT)
• John Flavin; Chris Markle; and Patrick Johnson (03/05/2011 11:40 AM EDT)
• Stephen Morris (03/05/2011 08:59 PM EDT)
• Adam Hajari (03/05/2011 11:51 PM EDT)
• Joshua Gunderson (03/07/2011 11:44 AM EDT)
• Jonathan Campbell & Shawn Simpson (03/07/2011 06:52 PM EDT)
• Álvaro Begué (03/07/2011 06:53 PM EDT)
• Wolfgang Kais (03/08/2011 05:40 AM EDT)
• Andrew D. Kidd (03/08/2011 02:01 PM EDT)
• John T. Robinson (03/08/2011 04:01 PM EDT)
• Jan Fricke (03/08/2011 05:49 PM EDT)
• Nyles Heise (03/09/2011 01:25 AM EDT)
• Thijmen Krebs (03/09/2011 12:38 PM EDT)
• Matt Dobrin (03/09/2011 07:10 PM EDT)
• M. Zecevic (03/10/2011 12:10 PM EDT)
• Dan Dima (03/10/2011 05:47 PM EDT)
• John Duffield (03/11/2011 05:22 AM EDT)
• Ante Kovacic (03/11/2011 08:01 AM EDT)
• Leif Jensen (03/11/2011 12:07 PM EDT)
• Harald van Dijk (03/11/2011 08:25 PM EDT)
• Greg Janée (03/13/2011 03:53 AM EDT)
• William Heller (03/14/2011 11:34 AM EDT)
• John G. Fletcher (03/14/2011 02:52 PM EDT)
• Daniel Bitin (03/14/2011 05:53 PM EDT)
• Armin Stranjak (03/14/2011 08:31 PM EDT)
• David Friedman (03/14/2011 08:56 PM EDT)
• Hani T. Dawoud (03/15/2011 10:14 AM EDT)
• Arash Bahrami & Taher Jamshidi (03/15/2011 06:37 PM EDT)
• Aliaksei Sanko (03/17/2011 08:17 AM EDT)
• Lu Wang & Siyu Yang (03/17/2011 02:32 PM EDT)
• Prathu Bharti Tiwari (03/17/2011 03:07 PM EDT)
• Mark Mixer (03/17/2011 09:59 PM EDT)
• Jamie Niemasik (03/18/2011 03:05 AM EDT)
• Suryaprasad Kareenahalli (03/18/2011 06:22 PM EDT)
• Klaus Hoffmann (03/19/2011 11:55 AM EDT)
• Hayk Aleksanyan (03/19/2011 02:27 PM EDT)
• Nir Avrahami (03/19/2011 02:57 PM EDT)
• Motty Porat (03/19/2011 06:34 PM EDT)
• Adam Daire (03/21/2011 06:58 PM EDT)
• Gale Greenlee (03/22/2011 11:41 AM EDT)
• Piet Orye (03/22/2011 04:26 PM EDT)
• Viacheslav Chernoy (03/22/2011 09:27 PM EDT)
• Clive Tong (03/23/2011 05:30 AM EDT)
• David P. Stigant (03/23/2011 02:39 PM EDT)
• Liubing Yu (03/28/2011 03:06 AM EDT)
• Nagy Zoltan (03/28/2011 07:34 AM EDT)
• David Cole (03/28/2011 01:21 PM EDT)
• Asaf S. (03/30/2011 06:12 AM EDT)
• Ante Turudic (03/30/2011 07:13 AM EDT)
• Antonio García Astudillo (03/30/2011 08:41 PM EDT)
• Karl D’Souza (03/31/2011 12:53 PM EDT)
• Stéphane Higueret (03/31/2011 02:30 PM EDT)
• Andrew Marut (03/31/2011 03:59 PM EDT)
• F&D Deal (03/31/2011 11:14 PM EDT)