4-6 Chip testing

Professor Diogenes has n supposedly identical integrated-circuit chips that in principle are capable of testing each other. The professors test jig accommodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the professor cannot trust the answer of a bad chip. Thus, the four possible outcomes of a test are as follows:

Chip A says Chip B says Conclusion

B is good A is good both are good, or both are bad

B is good A is bad at least one is bad

B is bad A is good at least one is bad

B is bad A is bad at least one is bad

a. Show that if at least [n/2] chips are bad, the professor cannot necessarily determine which chips are good using any strategy based on this kind of pairwise test. Assume that the bad chips can conspire to fool the professor. Now you will design an algorithm to identify which chips are good and which are bad, assuming that more than the upper bound [n/2] of the chips are good. First, you will determine how to identify one good chip. (5 points)

b. Show that [n/2] pairwise tests are sufficient to reduce the problem to one of nearly half the size. That is, show how to use [n/2] pairwise tests to obtain a set with at most [n/2] chips that still has the property that more than half of the chips are good. (7 points)

c. Show how to apply the solution to part (b) recursively to identify one good chip. Give and solve the recurrence that describes the number of tests needed to identify one good chip.

You have now determined how to identify one good chip. (7 points)

d. Show how to identify all the good chips with an additional (n) pairwise tests. (6 points)