Professor Diogenes has n supposedly identical integrated-circuit chips that in p

Question

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:

a) 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.

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 bn=2c pairwise tests are sufficient to reduce the problem to one of nearly half the size.

c) Show that the good chips can be identified with Big O(n) notation pairwise tests, assuming that more than n=2 of the chips are good. Give and solve the recurrence that describes the number of tests.

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

Explanation / Answer

Solution :-

a) Let g be the number of good chips and n-g be the number of bad chips. Also, assume n-g > g. From this assumption we have that we can always find a set G of good chips and a set B of bad chips of equal size g. Now, assume that the set B of bad chips conspire to fool the professor in the following way: for any test made by the professor, they declare themselves as ‘good’ and the chips in G as ‘bad’. Notice that the chips in G report correct answers and then exhibit a symmetric behaviour: they declare themselves as ‘good’ and the chips in B as ‘bad’. This implies that whichever is the strategy based on the kind of test considered and used by the professor, the behaviour of 5 the chips in G is indistinguishable from the behaviour of the chips in B. This does not allow the professor to determine which chips are good.

b) Assume n is even. Then we can match chip in pairs (c2i-1, c2i), for i = 1; : : : ; n/2 and test all these pairs. Then we throw away all pairs of chips that do not say ‘good, good’ and finally we take a chip from each pair. In this way, the final set contains at most n/2 chips and we are still keeping more good chips than bad ones, since all the pairs that we have discarded contain at least a bad chip.

Now, assume n is odd. Then, we test [n/2] pairs constructed as before; this time, however, we don’t test one chip, say, cn. Our final set will contain one chip for every pair tested that reported ‘good, good’. Moreover, according to whether the number of such chips has the form 4k + 3 or 4k + 1, we discard chip cn or we put it into our final set. Now, why this construction works ? First of all, as in the case in which n is even, by discarding all pairs of chips that report anything but ‘good,good’, we discard pairs of chips in which at least one is bad, and thus we still keep more good chips than bad ones. Now, assume that we have discarded the pairs of chips that report anything but ‘good,good’, and we are left with 4k+ 3 chips, for some integer k. Then, in this case there are at least 2k + 2 good chips and thus there are at least k + 1 pairs of ‘good,good’ chips, and at most k pairs of ‘bad,bad’ chips. Thus chip cn can also be discarded, and only a chip in each of these 2k + 2 pairs is not discarded. Finally, assume that we have discarded the pairs of chips that report anything but ‘good,good’, and we are left with 4k + 1 chips, for some integer k. Then, in this case there are at least 2k + 1 good chips.

Now, assume cn is bad; then there are at least 2k + 2 good chips, that is, k + 1 pairs of ‘good,good’ chips; and at most k 1 pairs of bad chips. Thus, taking a single chip from every pair, plus cn gives us at least k + 1 good chips and at most (k - 1) + 1 = k bad chips; that is, a majority of good chips and our final set is at most of size dk=2e. On the other hand, assume cn is good. Then we have at least k pairs of ‘good,good’ chips and taking a chip from each pair plus cn gives us a majority of good chips and a final set of size at most [k/2].

c) If at least n/2 of the chips are good, using the answer to question b), we can compute a single good chip. Now, in order to find all good chips, we can just test the good chip with all the others: for each pair of this type, knowing that at least one of the two chips in the pair is good is enough to decide whether the other chip is good or not. This last stage takes n - 1 more tests.

Then, in order to prove that the good chips can be found with (n) pairwise tests, we just need to show that the number of tests to find a single good chip is (n). To show this, we can write the number of tests T (n) that we do in the answer to question b) as

T (n) < T ([n/2]) + [n/2];

and T (1) = 0. The solution to this recurrence is T (n) = (n) and can be computed for instance by arguing and proving by induction that T (n) < 2[log n] .

Below is the Python code for the given question:

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.