Algorithm to solve a puzzle

Question

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:

1. if the outcome is fc, we know the chips were XF
2. 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

Answer 1

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.