|
|
 |
Условие
В компанию из N человек пришел журналист. Ему известно, что в этой
компании есть человек Z, который знает всех остальных членов компании,
но его не знает никто. Журналист может к каждому члену компании обратиться
с вопросом: "Знаете ли вы такого-то?"
Найдите наименьшее количество вопросов, достаточное для того, чтобы
наверняка найти Z.
(Все отвечают на вопросы правдиво. Одному человеку можно задавать
несколько вопросов.)
Подсказка
Можно ли что-нибудь сказать про членов компании А и В, если А знает В
(если А не знает В)?
Решение
Для того, чтобы прямо определить что данный человек Z, надо
задать 2*(N-1) вопросов: N-1 ему самому (знает ли он каждого члена
компании) и N-1 остальным членам компании (знают ли они его). Ясно,
что такой путь вряд ли оптимальный.
Рассмотрим метод исключения. Очевидно, что Z в компании может быть
только один.
Пусть журналист спросил А, знает ли он В. Тогда если А не знает В,
то А - не Z, если А знает В, то В не Z. Таким образом, с каждым
вопросом вне зависимости от ответа журналист сокращает перебор на
одного человека. Ясно, что он уложится за N-1 вопросов, так как
достаточно отмести N-1 человека, а оставшийся будет Z.
Ответ
N-1.
