Ponder This Challenge - December 2007 - Finding intermittently failing parts

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

Solution

• Click here to view the solution

  Ponder This Solution:

  The answers are:

  1. 4.0000
  2. 3.7683 (2eln(2), a=1/e=.367879)
  3. 3.5000
  4. 3.1546 (5*ln(2)/ln(3))
  5. 3.1063 (1/(H(.4)-.8*H(.25)) where H is the binary entropy function)

  A sketch of the proofs follows.

  1. Since each test fails .5*.5=.25 of the time, it takes an average of 4 tests to cut the problem size in half. So the total expected number of tests will be 4*log2(n).
  2. Each test will fail .5a of the time. So it takes 2/a tests on average to reduce the problem size by 1/a. So on average the total number of tests will be (2/a)ln(n)/ln(1/a) = 2ln(n)/(-aln(a)). So we wish to maximize -aln(a). Simple calculus shows we should pick a=1/e. So the answer is 2eln(n) = 2eln(2)(ln(n)/ln(2)) = 2eln(2)*log2(n).
  3. Let m be the average number of tests required to identify a failing subgroup (and cut the problem size in half). It is easy to see that m = .251 + .252 + .5*(m+2) or .5*m = 1.75 or m=3.5.
  4. Let m be the average number of tests required to identify a failing subgroup (and thereby cut the problem size by a fact of 3). Then m = (1/6)1 + (1/6)2 + (1/6)3 +(1/2)(m+3) so .5m =2.5 or m=5. So the average number of tests required to isolate the defective part is 5ln(n)/log(3) = (5ln(2)/ln(3))(ln(n)/ln(2)).
  5. We wish to reduce the uncertainty (entropy) of the position of the bad part by as much as possible on average with each test. Assume initially that each part is equally likely to be bad. As we proceed we will update the probabilities based on the result of each test. Suppose we test a subgroup which contains the bad part with probability p. The initial entropy (where we are just counting the entropy of the bad part being within the tested subgroup or not) is H(p). With probability p/2 this is reduced to zero. Otherwise with probability 1-p/2 it becomes H((p/2)/(1-p/2)). So to maximize the entropy reduction we must maximize H(p)-(1-p/2)*H((p/2)/(1-p/2)). Simple (but tedious) calculus shows the maximum occurs for p=.4 and has value H(.4)-.8*H(.25) = .321928 (using the binary entropy function). Since the initial entropy is log2(n) the total number of tests required to reduce this to 0 will be log2(n)/.321928 = 3.1063*log2(n). This is a lower bound but it is reasonably easy to see that it can be achieved by always testing subgroups which have .4 probability of containing the defective part. By including the highest probability (of being defective) parts first we can assure the probabilities remain reasonably even as the algorithm proceeds.

  ---

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

Solvers

• Part 5 correct (None)
• 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 (None)
• 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 (12.04.2007 @07:44:26 AM EST)
• 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)