Ponder This

December 2007

<<November December January>>

Ponder This Challenge:

Suppose we have a large number, n, of parts and know at least one is defective. If we can test any number of parts at once (learning whether they are all good or at least one is defective) then it is well known that a binary search will identify a defective part after log2(n) tests.

This month's puzzle concerns a variation on this problem in which the defective part only fails intermittently. Assume when the bad part is tested (by itself or with other parts) it fails half the time and passes half the time. The following questions concern how many tests on average it takes various algorithms to identify a single defective part out of a large number n.

You should ignore any lower order terms arising from the fact that you can only test integral numbers of parts at once. Express the answers as C*log2(n) where C is a constant given to 4 decimal places (ie 1.0000 for the original problem).

1. Suppose we use the following algorithm. Select a subgroup of size .5*n at random and test it. If it passes repeat with different random subgroups of size .5*n until you find a subgroup which fails. Then recursively apply the algorithm to smaller groups until you have isolated the bad part. How many tests on average will this take?
2. Use the algorithm in 1) except you test random subgroups of size a*n instead of .5*n. What is the optimal value of a and how many tests on average will be required?
3. Divide the parts at random into 2 equal subgroups and test them alternatively until one fails. Then apply the algorithm recursively. How many tests on average will be required to isolate the bad part.
4. Same as 3) except at each stage the parts are divided into 3 equal subgroups which are tested in turn until one fails. Again how many tests on average will be needed to find the bad part?
5. (Not required for credit) The algorithm in 4 is pretty good but not optimal. How many tests does the optimal algorithm require?

As usual we request that you only submit answers you have worked out yourself.

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: 12/03/2007 @ 05:15 PM EDT
Solution: 01/02/2008 @ 01:30 AM EDT
List Updated: 01/03/2008 @ 10:30 AM EDT

People who answered correctly:

Part 5 correct
Erik Hostens (12.05.2007 @04:31:59 PM EST)
Eugene Vasilchenko (12.06.2007 @12:42:17 PM EST)
V. Balakrishnan (12.06.2007 @05:40:52 PM EST)
Arthur Breitman (12.10.2007 @07:00:50 PM EST)
Wu Hao (12.12.2007 @11:07:50 PM EST)
Austin Shapiro (12.13.2007 @01:55:46 PM EST)
Fred Batty (12.14.2007 @02:43:31 PM EST)
Jiri Navratil (12.14.2007 @06:14:34 PM EST)
Alan Murray (12.16.2007 @12:40:39 AM EST)
Jochen Hoenicke (12.16.2007 @07:33:40 PM EST)
Andreas Eisele (12.21.2007 @09:14:31 AM EST)
Dharmadeep Muppalla (12.30.2007 @01:36:59 AM EST)
Dan Dima (12.31.2007 @10:01:11 AM EST)

Parts 1-4 correct
Dan Dima (12.03.2007 @06:39:14 PM EST)
V Balakrishnan (12.03.2007 @07:05:21 PM EST)
Mark Pilloff (12.03.2007 @08:11:27 PM EST)
Henry Bottomley (12.03.2007 @10:37:53 PM EST)
John Ritson (12.03.2007 @11:04:16 PM EST)
Alan Murray (12.04.2007 @03:41:43 AM EST)
Wu Hao (12.04.2007 @07:30:25 AM EST)
Micha Anholt and Eyal Gurgi (12.04.2007 @07:44:26 AM EST)
Preeyan Parmar (12.04.2007 @10:12:25 AM EST)
Gary M. Gerken (12.04.2007 @11:20:36 AM EST)
Karthik Tadinada (12.04.2007 @11:35:22 AM EST)
Frank Yang (12.04.2007 @01:03:56 PM EST)
Fred Batty (12.04.2007 @01:57:52 PM EST)
Mike Seidel (12.04.2007 @02:35:58 PM EST)
Joe Fendel (12.04.2007 @04:11:55 PM EST)
Eugene Vasilchenko (12.04.2007 @04:20:34 PM EST)
John Tromp (12.04.2007 @04:39:38 PM EST)
Benedikt Engels (12.04.2007 @07:02:00 PM EST)
Mark Perkins (12.04.2007 @07:42:13 PM EST)
Daniel Li (12.04.2007 @09:23:59 PM EST)
Wolfgang Kais (12.05.2007 @12:42:28 AM EST)
Christian Blatter (12.05.2007 @05:36:39 AM EST)
Martin Thiim (12.05.2007 @07:48:27 AM EST)
Itzik (12.05.2007 @08:21:54 AM EST)
William C Hasenplaugh (12.05.2007 @12:49:23 PM EST)
John T. Robinson (12.05.2007 @01:50:23 PM EST)
Ashish Srivastava (12.05.2007 @03:04:19 PM EST)
Erik Hostens (12.05.2007 @04:31:59 PM EST)
Miguel Catalina (12.05.2007 @06:45:49 PM EST)
Ylvaro Begu (12.05.2007 @06:52:27 PM EST)
Chris Lomont (12.06.2007 @02:29:45 PM EST)
Willem Buiting (12.06.2007 @03:28:44 PM EST)
Andreas Eisele (12.06.2007 @03:57:57 PM EST)
Samantha Casanova (12.06.2007 @04:20:24 PM EST)
Amos Guler (12.07.2007 @10:30:13 AM EST)
James Fraser (12.07.2007 @11:37:09 AM EST)
Don Rice (12.07.2007 @01:26:54 PM EST)
Vladi Tsipenyuk (12.07.2007 @05:47:36 PM EST)
Mithil Ramteke (12.09.2007 @02:38:02 PM EST)
Jiri Navratil (12.09.2007 @03:10:45 PM EST)
Albert Stadler (12.10.2007 @03:33:01 AM EST)
Arthur Breitman (12.10.2007 @03:50:33 PM EST)
Eric Wong (12.10.2007 @07:22:17 PM EST)
Stephen Merriman (12.10.2007 @10:23:03 PM EST)
John Fletcher (12.10.2007 @10:47:04 PM EST)
Andrej Tolic (12.10.2007 @11:45:45 PM EST)
Kai Guttmann (12.11.2007 @05:58:03 PM EST)
Mark Thornquist (12.11.2007 @06:28:36 PM EST)
Ilan Algor (12.12.2007 @01:08:11 AM EST)
Ian Smith (12.12.2007 @10:27:49 AM EST)
Nyles Heise (12.12.2007 @01:21:47 PM EST)
Austin Shapiro (12.13.2007 @01:55:46 PM EST)
John Stebbins (12.13.2007 @11:23:02 PM EST)
Hongcheng Zhu (12.13.2007 @11:32:29 PM EST)
Ranchu Mathew (12.14.2007 @12:16:09 PM EST)
Phil Muhm (12.14.2007 @12:25:33 PM EST)
Paolo Massaro (12.14.2007 @04:43:47 PM EST)
Jan van Delden (12.15.2007 @11:22:43 AM EST)
Jochen Hoenicke (12.16.2007 @07:33:40 PM EST)
Dion Harmon (12.16.2007 @10:04:21 PM EST)
Rashid Zia (12.17.2007 @03:08:46 AM EST)
Luciano Tsiros (12.17.2007 @12:49:36 AM EST)
Lawrence E. Flynn (12.18.2007 @10:03:42 PM EST)
Paolo Massaro (12.19.2007 @11:11:59 PM EST)
Maxim G. Smith (12.20.2007 @02:43:08 PM EST)
Peter Korteweg (12.21.2007 @07:30:48 PM EST)
Reiner Martin (12.22.2007 @06:31:55 PM EST)
Rani Hod (12.24.2007 @10:21:10 AM EST)
Andrea Andenna (12.26.2007 @04:35:54 AM EST)
Arnab Bose (12.26.2007 @09:53:05 AM EST)
Jamieson Cobleigh (12.27.2007 @03:40:04 PM EST)
David Friedman (12.27.2007 @04:25:03 PM EST)
Dan Adkins (12.28.2007 @07:10:34 PM EST)
Karl D'Souza (12.29.2007 @05:35:11 PM EST)
Chris Shannon (12.30.2007 @11:28:30 PM EST)
Ole Martin (12.31.2007 @11:18:59 AM EST)
Dion Harmon (12.31.2007 @11:45:55 AM EST)
Hassan Masum (01.01.2008 @12:10:34 AM EST)
Ehud Schreiber (01.01.2008 @07:57:31 AM EST)

Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.