Задача
Детектив Ниро Вульф расследует преступление. В деле замешаны 80 человек, среди которых один – преступник, еще один – свидетель преступления (но неизвестно, кто это). Каждый день детектив может пригласить к себе одного или нескольких из этих 80 человек, и если среди приглашенных есть свидетель, но нет преступника, то свидетель сообщит, кто преступник. Может ли детектив заведомо раскрыть дело за 12 дней?
Решение
Первый способ. Занумеруем 80 подозреваемых четырёхзначными троичными числами abcd от 0001 до 2222 (таких чисел ровно 34 – 1 = 80).
В k-й день (k = 1, 2, ..., 12) Ниро Вульф приглашает к себе тех подозреваемых, номера которых удовлетворяет k-му из равенств a = 0, a = 1, a = 2,
b = 0, b = 1, b = 2, c = 0, c = 1, c = 2, d = 0, d = 1, d = 2. Тогда в один из этих дней он пригласит к себе свидетеля, но при этом не пригласит преступника, так как их номера отличаются хотя бы в одной цифре. Второй способ. Разобьём подозреваемых на 16 групп по 5 человек. Занумеруем группы четырёхзначными двоичными числами abcd от 0000 до 1111, а её членов занумеруем числами от 1 до 5.
В k-й день (k = 1, 2, ..., 8) Ниро Вульф приглашает к себе подозреваемых из групп, номера которых удовлетворяет k-му из равенств: a = 0, a = 1,
b = 0, b = 1, c = 0, c = 1, d = 0, d = 1. Если преступник и свидетель попали в разные группы, то преступление будет раскрыто в один из этих дней.
Предположим, что свидетель находится в одной группе с преступником. Обозначим через m и n номера свидетеля и преступника в этой группе соответственно. На 9-й день Ниро Вульф приглашает из каждой группы подозреваемых с номерами 1 и 2, на 10-й день – подозреваемых с номерами 3 и 4, на 11-й день – подозреваемых с номерами 1, 3 и 5, на 12-й день – подозреваемых с номерами 2, 4 и 5. Тогда найдётся один из этих дней, в который из каждой группы были приглашены подозреваемые с номером m, но при этом не были приглашены подозреваемые с номером n. Значит, в этот день преступление будет раскрыто. Третий способ. Покажем, что Ниро Вульф сможет найти преступника даже за 9 дней. Для этого сопоставим каждому подозреваемому свой номер – девятизначное двоичное число, четыре цифры которого – единицы, а пять – нули (это возможно, так как всего таких чисел 
).
В k-й день (k = 1, 2, ..., 9) Ниро Вульф приглашает к себе тех подозреваемых, k-я цифра номера которых равна 1. Поскольку все номера содержат ровно по 4 единицы, найдётся такое число m от 1 до 9, что на m-м месте у свидетеля стоит единица, а у преступника – ноль. Значит, в m-й день свидетель будет приглашен к Ниро Вульфу без преступника, и преступление будет раскрыто.
Ответ
Может.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь