I have the following problem:
nchips [note: these are VLSI chips] out of which majority of chips are good, we need to find one good chip. The only test that we can apply is on a pair of chips that answers if both chips are good or both are bad. The second part is to find a good chip if some tests might produce a wrong result. Also, the results are systematic meaning that if a pair gives wrong result, it will always give the wrong result.
I have solved the first problem using divide and conquer approach where I reduce the problem set to at least half every time. This can be done by simply performing tests on n/2 distinct pairs every time and keeping those pairs that answer a YES (i.e. both good or bad). I am unable to solve the second part of the problem.
A wrong result means that even if two chips are good or bad, the test might answer a NO. Also note that the percentage of wrong tests is very low.
How can I go about solving this problem?