we are given n chips which may be working or defective. Aworking chip behaves as follows: if we connect it to another chip,the original chip will correctly output whether the new connectedchip is working or is defective. However, if we connect a defectivechip to another chip, it may output any arbitrary answer(defective---->might say the other one is working/defective).
In the class, we saw that if strictly more than half the chipsare working, then there is an algorithm that finds a working chipusing O(n) tests.
1) Prove that even when we only have a single working chip and asingle defective chip (i.e.,n = 2), there is no algorithm that canfind the working chip in general.
