Деревья и остовные деревья

Пример. Спросим про пары и а затем про все пары вида где Докажем, что за первые три вопроса мы выясним составы кружков и Посмотрим на любого человека. Если он не ходит ни в один из этих кружков, то его имя не будет названо ни разу, и это ни с чем не перепутаешь. Если он входит только в один кружок, то его имя всплывёт в двух вопросах, как посещающего один кружок. При этом по этим двум парам мы восстановим, в какой кружок он ходит. Если он ходит в два кружка, то однажды он появится, как посещающий два кружка, и дважды — как посещающий один из двух. В этой ситуации легко вычисляется, куда он ходит. Если он ходит во все, то во всех парах покажется, как посещающий оба, и тоже получится вычислить, что он во все ходит. То есть про любого человека мы поймём, куда он ходит, а это и значит, что вычислим составы всех кружков. Теперь, зная, кто ходит в первый кружок, после вопроса легко вычисляем, кто ходит в кружок

Оценка. Будем считать, что в школе учеников. Каждому ученику сопоставим уникальное подмножество кружков и направим его ровно в кружки из его подмножества. Предположим, что после вопросов удалось выяснить составы всех кружков. Это значит, что мы научились различать всех учеников. Рассмотрим граф, вершины которого — кружки. Соединим вершины ребром, если мы спросили про эту пару кружков. В графе вершин и рёбер, значит, хотя бы в одной компоненте связности рёбер меньше, чем вершин, то есть эта компонента связности — дерево. А вершины дерева можно правильным образом покрасить в два цвета. Обозначим множества вершин первого и второго цвета и Тогда школьник, который ходит только в кружки множества и школьник, который ходит только в кружки множества по ответам не отличимы. Во всех вопросах про эту компоненту связности оба назывались как ходящие в один из двух кружков.