IBM 十二月

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?

所有跟帖： 

• 回复：IBM 十二月 -于德利- ♂ (134 bytes) () 12/03/2007 postreply 23:43:11

• Is golden ratio better for quesion #2? -endofsuburbia- ♂ (0 bytes) () 12/04/2007 postreply 09:34:08

• 对2xlogx(n)求导数，1/lnx-1/(lnx)^2=0，所以，x=2 -于德利- ♂ (0 bytes) () 12/04/2007 postreply 10:09:48

• x=e? -康MM- ♀ (0 bytes) () 12/04/2007 postreply 15:07:03

• 对，x=e！ -于德利- ♂ (0 bytes) () 12/04/2007 postreply 15:39:45