вспомнил простую, но милую задачу из КЛР
есть n микросхем, которые умеют тестировать друг друга. некоторые микросхемы бракованные. в парном тесте две микросхемы тестируют друг друга. небракованная микросхема говорит про другую из пары правильно, бракованная она или нет. бракованная может говорить что угодно.
тогда
а) если больше половины микросхем бракованные, установить, какие из них какие, парными тестами нельзя
б) если меньше половины микросхем бракованные, то можно установить, какие из них какие, за O(n) парных тестов.