|
|
 |
Условие
Полиция задержала 50 человек, из которых 35 – преступники, которые говорят, что захотят, а 15 – свидетели, которые всегда говорят правду. Все задержанные знают, кто преступники. Какое наименьшее число человек достаточно выбрать, чтобы спросив потом у каждого, кто именно преступники, по ответам вычислить хотя бы одного преступника?Решение
Оценка сверху. Выберем 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 любых неопрошенных. Так
как мы не можем понять, какая из версий настоящая, то и преступника мы
найти не сможем, ведь любой человек в какой-то из версий свидетель.
