Решение задачи 156

Условие:

Имеется 80 подозреваемых, среди которых один убийца и один свидетель. Пуаро каждый день приглашает к себе любое количество подозреваемых. Если окажется, что в этой группе есть свидетель, но нет убийцы, то свидетель расскажет всю правду, и Пуаро раскроет это дело. Сможет ли Пуаро за 12 дней наверняка раскрыть дело?

Решение:

Пронумеруем людей числами от 1 до 80, и запишем каждый номер в троичной системе так, чтобы все номера состояли из четырех цифр (у первого номер 0001, у второго -- 0002,.., у 80-го -- 2222). Получается, мы закодировали каждого человека четырьмя цифрами, причем каждая цифра равна 0, 1 или 2, и все коды попарно различны. Тогда пригласим в первый день людей, у которых первая цифра в коде 0. Во второй день пригласим людей, у которых первая цифра в коде 1. И так далее, в двенадцатый день пригласим тех, у кого последняя (четвертая) цифра в коде 2. Таким образом, каждый человек будет приглашен 4 раза.

У убийцы и свидетеля различные коды, значит найдется позиция, на которой их коды различаются (i-ая позиция). Тогда найдется день, когда Пуаро пригласит тех людей, у которых на i-ой позиции стоит цифра, такая же как у свидетеля, но не у убийцы. Значит, свидетель будет приглашен, а убийца нет, и Пуаро раскроет дело.

Ответ: Да.

Замечание 1: Пуаро справился бы с делом, даже если бы был 81 подозреваемый, а не 80. Тогда нумерация бы начиналась с нуля, и нулевой человек имел бы код 0000.

Замечание 2: Из решения задачи не следует, что 12 -- минимальное число дней, которое нужно Пуаро для раскрытия дела. Возможно, существует тактика, следуя которой, Пуаро наверняка бы нашел убийцу менее, чем за 12 дней.