A Computer Science/Math Algorithm Question

Calling all Math and CS Theory wizards, here's an algorithm question that I need help with. This would require use of recurrence and divide and conquer strategy:

There are n supposedly identical VLSI chips that in principle are capable of testing each other. 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 answer of a bad chip cannot be trusted. 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 more than n/2 chips are bad, we 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 the tester.


b. Consider the problem of finding a single good chip from among n chips, assuming that more than n/2 of the chips are good. Show that floor(n/2) pairwise tests are sufficient to reduce the problem to one of nearly half the size.


c. Show that the good chips can be identified with Theta(n) pairwise tests, assuming that more than n/2 of the chips are good. Give and solve the recurrence that describes the number of tests.