Комбинаторика на устном туре Турнира Городов

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

_________________________________________________________________________________________________________________________________________________________________________________

Выберем 47 человек и каждого спросим «Кто из жителей преступники?». Пусть каждый назвал 35 человек и никто не назвал себя, иначе преступник определяется очевидно. Разобьем всех людей на групшы так, что внутри одной группы ответы одинаковые.

Заметим, что в одной группе не больше 15 человек, иначе каждый из них обвинил бы менее 35 человек. Докажем, что найдется группа, в которой менее 12 человек.

Действительно, если в каждой группе хотя бы 12 человек, то если этих групп хотя бы 4 , то всего людей хотя бы , а если групп не более, чем 3 , то всего людей не более, чем — противоречие.

Возьмем ту группу, где меньше 12 человек. Если бы кто-то из них был свидетелем, то вместе с ним свидетелем могли быть только люди из его группы и неопрошенные люди, то есть менее 15 человек, противоречие. Значит, люди этой группы — преступники.