March 2011
<<February March April>>
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
Challenge:
03/01/2011 @ 10:00 AM EST
Solution:
04/01/2011 @ 10:00 AM EST
List Updated:
04/01/2011 @ 10:00 AM EST
People who answered correctly:
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)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.