I think its a problem similar to finding out one good chip and one bad chip in the given set. If you get a good chip then you can find out the bad chip.
I think its a problem similar to finding a soilder which has a infected blood or so... there is some problem based I dont remember. I this case you should devide the chips in n/2 set and try to figure out one good chip. something like devide and quanqer algo used in merge sort. Thank You, Mayur On Nov 23, 11:36 am, LostL <[EMAIL PROTECTED]> wrote: > Here is the description of this problem: > -------------------------------------------------------- > Professor Diogenes has n supposedly identical VLSI[1] 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 > answer of a bad chip cannot > be trusted. 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 > 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 ⌊n/2⌋ 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 Θ(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. > ---------------------------------------------------------- > Solutions/hints will be appreciated. > > Thanks! --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
