A professor has n VLSI chips that can be placed on a test bed 2 at a time, where they test each other.

logic/faulty.chips New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

A professor has n VLSI chips that can be placed on a test bed 2 at a
time, where they test each other.  A good chip reports if the other is
bad, but a bad chip cannot be trusted.

Result:
Each says other is good: then both chips are good or both are bad.
One says the other is bad: then at least one of the two is bad.

Show that if more than n/2 of the chips are bad, then no strategy can
determine the good chips.

Consider the problem of finding 1 good chip.  Show that this requires
n/2 comparisons to reduce the problem to half its original size.

Show that it requires O(n) comparisons to find the good chips if more
than n/2 of them are good.  That should be theta(n): theta means it is
an upper and lower bound.

[ Editor: the poser (damion5940@my-dejanews.com) thought the original
form of the problem involved the weights of coins. ]

Show solution

Let's prove something different; P(n) will be the statement "Given a
set of n chips with less than half faulty, we can identify a non-faulty
chip in linear time."  This is logically equivalent to determining all
chips in linear time, because once we've found a good chip we can test
it against all the others with an additional n-1 trials.

So, we'll proceed by general induction.  Let a natural number n be
given, and assume that P(n') is true for all n' < n.  Let a set of n
chips be given, and let m be the number of faulty chips in the lot, so
that m/n < 0.5.  Pair up the chips, leaving one out if n is odd, and do
the floor(n/2) tests.  If all of the tests revealed at least one
failure, then the only way that there could be less than half failed
chips is if we started with an odd sample set; then the untested chip
is good.  Assuming that at least one test was double-positive, lay
aside all of the pairs where a failure result was noted by either of
the chips and the odd chip (if there was one).  So, you're left with
some positive number of pairs of chips where each chip verified the
goodness of the other: a pair of chips are either both good or both
faulty.  Pick one of the chips from each of those pairs and lay those
aside as well.

Let n' be the number of chips that have not been laid aside, and let m'
be the number of them that are faulty.  Can it be that m'/n' >= 0.5?
No, because the failure chips that were laid aside are at least half
and possibly more (we could have paired up two bad chips that produced
failure results) and the bad ratio before we started was less than
half.  So, by the induction hypothesis, we can find a good chip from the
set of n' in linear time.  That time plus the floor(n/2) we took keeps
the trial in linear time for us.  QED.

If half or more of the chips were faulty in such a way that they would
say that a faulty chip was good and a good chip was faulty.  Then even
if you did all n(n-1)/2 tests and divided the chips into two piles, you
would know that one was all good and the other was all faulty, but you
wouldn't know which pile was which.

-- Matthew Daly <mwdaly@pobox.com>