Problem 4.5

Chip testing

Professor Diogenes has $n$ supposedly identical 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.

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

1. Show that if more than $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.
2. 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.
3. Show that the good chips can be identified with $\Theta(n)$ pairwise tests, assuming that more than $n/2$ chips are good. Give and solve the recurrence that describes the number of tests.

If more than half are bad

Lets say that there are $g < n/2$ good chips. The same amount of the remaining bad chips can choose to act similar to good chips. That is, they can identify each other as good and all other as faulty. Since this is what the good chips would do, both groups are symmetric in regards to the operation of parwise comparison. No strategy can distinguish between the two groups.

Finding a single good chip in logarithmic time

We split the chips in groups of two and compare them. We can take one of the chips if the outcome is the first one (both are good or both are bad) and but both away otherwise. When putting away, we're removing at least one bad chip for every good one we remove. Out of the pairs we've chosen a chip from, there would be more good chips than bad chips (there would be more good pairs, because the good chips are more than the half). Now we have at most $n/2$ chips, where at least half of them are good.

Finding the good chips

The recurrence for finding at least one good chip is:

$$ T(n) = T(n/2) + n/2 $$

By the master method, this is $\Theta(n)$. After we've found one, we can compare it will all others, which is a $\Theta(n)$ operation.

Python code

import random

class GoodChip:
    def good(self):
        return True

    def check(self, other):
        return other.good()

class BadChip:
    def good(self):
        return False

    def check(self, other):
        return [True, False][random.randint(0, 1)]

def jig(a, b):
    return [a.check(b), b.check(a)]

def diogenes(chips, verbose = False):
    def find_single(chips):
        if len(chips) <= 2:
            return chips[0]
        else:
            halfpoint = len(chips) // 2
            pairs     = zip(chips[0:halfpoint], chips[halfpoint:halfpoint * 2])
            kept      = [a for (a, b) in pairs if jig(a, b) == [True, True]]

            if len(chips) % 2 == 1:
                kept.append(chips[-1])

            return find_single(kept)

    good = find_single(chips)
    return [chip for chip in chips if jig(good, chip) == [True, True]]