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 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

1. 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.

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\) of the chips are good. Give and solve the recurrence that describes the number of tests.

The key insight from the test outcomes table is that when both chips agree (both say “good”), we can’t tell if they’re both actually good or both conspiring liars. This ambiguity is central to the problem.

A

If at least \(n/2\) chips are bad, they can conspire to fool the professor.

Proof by construction:

Suppose we have \(n\) chips where \(\lceil n/2 \rceil\) are bad and \(\lfloor n/2 \rfloor\) are good.

The bad chips can adopt this strategy:

• When a bad chip tests another bad chip, both report “good”
• When a bad chip tests a good chip, the bad chip reports “bad”
• Good chips always report truthfully

From the professor’s perspective, there are two indistinguishable scenarios:

1. The chips reported as “good” by the bad majority are actually the good chips
2. The bad chips are lying, and they themselves form the “good” group

Since \(\lceil n/2 \rceil \ge \lfloor n/2 \rfloor\) , these scenarios cannot be distinguished through testing alone.

B

The strategy here is beautifully simple: pair up chips and test them against each other. If they disagree, we know at least one is bad, so we discard both. If they agree, we keep one. The key insight is that this process maintains the property that good chips remain in the majority, allowing us to recursively shrink the problem.

Algorithm: Use \(\lfloor n/2 \rfloor\) pairwise tests to reduce the problem size.

FIND-GOOD-CHIP(S):

1. If \(\vert S \vert = 1\), return the chip in \(S\)
2. Pair up chips arbitrarily, leaving one unpaired if \(\vert S \vert\) is odd
3. Test each pair:
   • If both chips agree (both say the other is good), keep one chip from the pair
   • If chips disagree, discard both
   • If there’s an unpaired chip, keep it
4. Let \(S'\) be the set of kept chips
5. Recursively call FIND-GOOD-CHIP(\(S'\))

Correctness:

• If we keep a chip from an agreeing pair, at least one is good (both could be good, or both bad)
• If we discard a disagreeing pair, at least one was bad
• If more than \(n/2\) chips are good initially, the good chips maintain a majority:
  • Agreeing good-good pairs: we keep 1 good
  • Agreeing bad-bad pairs: we keep 1 bad
  • Disagreeing pairs: we remove at most 1 good and at least 1 bad

Analysis of majority preservation:

Why does the good majority persist? Let’s think about what happens to each type of pair. When two good chips test each other, they both say “good” and we keep one good chip. When two bad chips test each other, they might lie and say “good,” and we keep one bad chip. When a good and bad chip test each other, they disagree, so we discard both. The crucial observation is that disagreeing pairs always remove at least one bad chip along with at most one good chip, which helps maintain or improve the good-to-bad ratio.

Let \(g\) = good chips, \(b\) = bad chips, with \(g > b\).

In each reduction:

• Good-good pairs: \(\le \lfloor g/2 \rfloor\) kept goods
• Good-bad pairs: \(\le \min(g,b)\) removed (at least this many bads removed)
• Bad-bad pairs: \(\le \lfloor b/2 \rfloor\) kept bads

After reduction: \(g' \ge \lceil g/2 \rceil\) and \(b' \le \lfloor b/2 \rfloor\)

Since \(g > b\): \(g'/b' > g/b > 1\), so the good majority is maintained.

Recurrence: \(T(n) = T(\lceil n/2 \rceil) + \lfloor n/2 \rfloor\)

This gives \(T(n) = \Theta(n)\).

C

Algorithm:

1. Use part B to find one good chip \(G\): \(\Theta(n)\) tests
2. Test \(G\) against all other \(n-1\) chips: \(n-1\) tests
3. Chips that \(G\) reports as “good” are good (\(G\) is truthful)
4. Chips that \(G\) reports as “bad” are bad

Total tests: \(\Theta(n) + (n-1) = \Theta(n)\)

Recurrence for part B:

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

Expanding:

\[\begin{align*} T(n) &\le T(n/2) + n/2\\ &\le T(n/4) + n/4 + n/2\\ &\le T(n/8) + n/8 + n/4 + n/2\\ &= T(1) + n(1/2 + 1/4 + 1/8 + \cdots)\\ &= \Theta(n) \end{align*}\]