An engineer has n supposedly identical integrated-circuit chips that in principle are capable of testing each other. The engineer 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 engineer cannot trust the answer of a bad chip. Assume that thenumber of good chips is greater than the number of bad chips. Thenanswer the following question:
Is it possible to design an algorithm that finds all the good chips after at most O(n log n) pairwise tests?