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