b) найдем одну правильную микросхему за O(n), и тогда ею за O(n) проверим все остальные:

поделим множество микросхем произвольно на пары,

если будет лишняя микросхема, то ее отложим;
заставим каждую пару проверить друг друга

если в какой-то паре хотя бы один результат "брак", то в этой паре хотя бы одна микросхема бракованная
поэтому отбросим все такие пары с браком, и получим множество пар, которые друг о друге отзываются хорошо
если это множество пар пусто, то отложенная микросхема - рабочая, иначе бы кол-во хороших было бы меньше кол-ва плохих

в каждой из оставшихся пар либо обе микросхемы рабочие, либо обе бракованные
наберем по одной микросхеме из каждой пары в новое множество микросхем

если в новом множестве нечетное кол-во микросхем, то хороших там снова больше, чем плохих,
иначе бракованных пар было бы больше и соответственно бракованных микросхем тоже больше

если в новом множестве четное кол-во микросхем, добавим туда отложенную микросхему
если до добавления там было одинаковое кол-во хороших и плохих, то отложенная микросхема была хорошая и после ее добавления стало больше хороших, чем плохих
если до добавления отложенной микросхемы хороших было больше, то и после добавления их останется больше, даже если отложенная микросхема была плохой
мы возвращаемся в начало и делаем по новой, пока не останется одна микросхема, она будет хорошей

кол-во итераций
2n + 2n/2 + ... + 2n/i^2 + ... 2n/k^2 = 2n*(1 + 1/2 + ... + 1/k^2) < 2n * 2