Professor Diogenes has n supposedly indentical integrated-circuit chips that in principle are capable of testing each other. The professor’s test jig accomodates 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:

\[\begin{array}{l l l} \text{Chip } A \text{ says} & \text{Chip } B \text{ says} & Conclusion \\ \hline B \text{ is good} & A \text{ is good} & \text{both are good, or both are bad} \\ B \text{ is good} & A \text{ is bad} & \text{at least one is bad} \\ B \text{ is bad} & A \text{ is good} & \text{at least one is bad} \\ B \text{ is bad} & A \text{ is bad} & \text{at least one is bad} \\ \end{array}\]

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.

Once the bad chips meet or exceed this \(n/2\) threshold, they can effectively fool the professor by adopting a counter-strategy that results in each pair producing the exact same output, regardless of how many good chips there may be. By pairing each bad chip with a good chip, all pairs would report Bad and Bad. Similarily by pairing each chip with another chip of the same kind (bad with bad, good with good) all pairs would report Good and Good. In both scenarios, the professor would have gained no information from their strategy and any attempt to select a good chip would be no better than making such a selection at random.

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 \(\lfloor n/2 \rfloor\) pairwise tests are sufficient to reduce the problem to one of nearly half the size.

We start with \(n\) chips and know that there are more good chips than bad chips. Divide all the chips into \(\lfloor n/2 \rfloor\) pairs, with 1 chip set aside in the event that \(n\) is odd. For each of the pairwise tests, if either chip reports the other is bad, discard both chips. If both chips report each other as good, discard one chip. Combine the set aside chip (if there was one) with all remaining chips and repeat this process. You will eventually be left with one chip and it is guaranteed that that chip is good.

At each point when you are discarding one or more chips, the property that there are more good chips than bad chips is always held. When you discard both chips, the table above tells us that at least one of them was bad. Discarding one chip from a pair that reports both are good could result in both actually being good, but this would always be offset by the discarding of bad chips from other pairs. In a similar way, this property guarantees that we will never reach a situation wherein we discard all remaining chips unless there is one set aside. This algorithm will continue until there is only one chip remaining, and when this happens the property that there are more good chips than bad chips will still hold, and thus that final remaining chip must be a good chip.

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.

The approach described by b is a recurrence of the following form:

\[T(n) \leq T( \lceil n/2 \rceil) + \lfloor n/2 \rfloor\]

Case 3 of the master method applies and we have \(T(n) = \Theta(n/2)\). With a single good chip found, we can then do a pairwise comparison with all remaining \(n - 1\) chips. Overall, this approach is \(\Theta(n/2 + n - 1) = \Theta(n)\).