IBM Research | Ponder This | December 2007 solutions
Skip to main content

Ponder This

December 2007

<<November December January>>

Ponder This Solution:

The answers are:

  1. 4.0000
  2. 3.7683 (2*e*ln(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 .5*a 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) = 2*ln(n)/(-a*ln(a)). So we wish to maximize -a*ln(a). Simple calculus shows we should pick a=1/e. So the answer is 2*e*ln(n) = 2*e*ln(2)*(ln(n)/ln(2)) = 2*e*ln(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 = .25*1 + .25*2 + .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 .5*m =2.5 or m=5. So the average number of tests required to isolate the defective part is 5*ln(n)/log(3) = (5*ln(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