Part (b) says that when there are more than half good chips and your goal is to find out ONE of them, you can use divide-and-conquer techniques and floor(n/2) pairwise tests can reduce the problem size to nearly half.
We notice that in a test, when "Good-Good" is reported, the two must be both good or both bad. Otherwise, they cannot be both good. So we'll choose any one from such groups and ignore all other groups.
When the number of chips is even, the situation is quite straightforward. Consider the extreme condition in which there are (n-1) bad chips and (n+1) good ones. The number of groups in which both two are good must be larger than the groups in which both two are bad. So after the "divide", the property that there are more than half good chips is preserved.
When the number of chips is odd, the problem becomes a little bit intricate. Again consider the extreme condition in which there are n bad chips and (n+1) good ones. We must take out a chip, namely X, and perform pairwise tests for the others. When X is bad, it is OK. But what if X is good? We can easily see that after the "divide", the number of good ones must be no smaller than the number of bad ones no matter what you take out. So when there are odd number of chips after the "divide", we can conclude that the property is actually preserved(Note that if there is exactly 1 left, then it must be good) and we can simply ignore X. Otherwise, we cannot tell whether X is good or bad, but from part (a) we know that when there are equal numbers of good chips and bad chips, we may not be able to distinguish any one as good if all bad chips can conspire. So just keep this unknown chip and proceed further. If the one taken out is good and all bad ones do conspire, at last we know X is in fact good. Otherwise, we will find another good one.
This post gives a more detailed explanation in Chinese.
No comments:
Post a Comment