Algorithm to solve a puzzle Firstly, note that this is from an exercise sheet, and we were asked to try and solve it, for a discussion.
We are given $n$ chips that can test each other in the following way: if two of the chips are connected,
then both determine whether the other one is faulty or correct. A correct chip decides properly about
the other, while a faulty chip can give an arbitrary answer. Assume, that more than half of the chips
are correct. Give an algorithm that uses less than $n$ tests of the above type to find a correct chip.
My attempt:
First, we categorize the possible outcome of different combinations. Chips will be in uppercase, their outcome will be lowercase.C/c = correct, F/f = fault. X will denote an unknown chip.
CF = {fc,ff}, CC = {cc}, FF = {fc,ff,cf,cc}, FC = {cf,ff}.
First set of observations:

*

*if the outcome is fc, we know the chips were XF

*if the outcome is cf, we know the chips were FX

My current idea is by first combining any 2 random chips together, then remove every outcome but cc, which can only be produced by FF or CC. Combine a chip from these 'cc'-pair with another chip from another 'cc'-pair. From here,if the possible combinations are
CC-FF = {fc,ff}, CC-CC = {cc}, FF-CC = {cf,ff}, FF-FF = {fc,ff,cf,cc}.
After this, I do not know how to proceed. Should I keep on focusing on just 'cc'- outcomes? Should I start eliminating faulty ones(by filtering out fc/cf). Of course, your own solution would also be very helpful to me. Thank You
 A: Use three piles 1, 2, 3, where originally all $n$ chips are in pile 1.
Repeatedly pick two chips from pile 1 and test. If the result is "cc" put one of the to pile 2 and the other to pile 3 (knowing that both chips are of the same type). In all other cases discard both. When discarding, we will always discard at least as many F as C, i.e., this method keeps the C chips in majority.
We repeat this until pile 1 is empty or has at most one chip X. We also know that the C/F statistics of pile 2 exactly equals that of pile 3.

*

*If no X was left ($n$ was even), move pile 2 to pile 1 and discard pile 3, and start over again.

*If an X was left, add it to either of the two piles, making one pile even and the other odd. If C is in minority in the odd pile, then there is at most a tie in the even pile, hence overall a minority of C, which is absurd. Therefore C is in majority in the odd pile. Move this pile to pile 1 and discard the other pile, and start over again.

Note that each test between two chips leads to removal of at least one of them: Either they are both discarded immediately, or one of them is discarded together with a whole pile. Hence after at most $n-1$ tests, we will have only one chip left, which must be C.
