Отыскание преступника: олимпиадная задача по теории алгоритмов

Оценка сверху.Выберем 47 человек и каждого спросим «Кто из жителей преступники?». Пусть каждый назвал 35 человек и никто не назвал себя, иначе преступник определяется очевидно. Разобьем всех людей на группы так, что внутри одной группы ответы одинаковые. Заметим, что в одной группе не больше 15 человек, иначе каждый из них обвинил бы менее 35 человек. Докажем, что найдется группа, в которой менее 12 человек. Действительно, если в каждой группе хотя бы 12 человек, то если этих групп хотя бы 4, то всего людей хотя бы $12\cdot 4 = 48 > 47$, а если групп не более, чем 3, то всего людей не более, чем $15\cdot 3 = 45 < 47$, противоречие. Возьмем ту группу, где меньше 12 человек. Если бы кто-то из них был свидетелем, то вместе с ним свидетелем могли быть только люди из его группы и неопрошенные люди, то есть менее 15 человек, противоречие. Значит, люди этой группы – преступники.Оценка сверху, 2-й способ. Выберем 47 человек и каждого спросим «Кто из жителей преступники?», и каждый из них назовет свое 35-элементное подмножество преступников. Заметим, что среди этих 47 человек не менее 12 свидетелей, поэтому они назовут одно и то же 35-подмножество. Далее, 35-подмножество назовем потенциально-преступным (п-п), если его назвали не менее 12 из 47 человек. Одно из п-п подмножеств должно в самом деле совпадать с множеством преступников. Но среди всех 50 человек есть человек $A$, входящий во все п-п 35-подмножества: действительно, п-п 35-подмножеств всего не более 3 (иначе опрошенных было бы не менее $4 \cdot 12 = 48$, и поэтому 15-элементные дополнения к п-п подмножествам накрывают не более 45 опрошенных. Значит $A$ – точно преступник.

Оценка снизу. Пусть мы опросили $k < 47$ людей. Опросим еще $46-k$ случайных людей из оставшихся. Разобьем 46 опрошенных людей на 4 группы по 11, 11, 11, 13 человек. Пусть группы, где 11 человек, будут отвечать на вопросы так, будто свидетели они и 4 неопрошенных человека, а группа из 13 человек будет отвечать на вопросы так, будто свидетели они и 2 любых неопрошенных. Так как мы не можем понять, какая из версий настоящая, то и преступника мы найти не сможем, ведь любой человек в какой-то из версий свидетель.