ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 35474
Тема:    [ Теория алгоритмов (прочее) ]
Сложность: 2+
Классы: 7,8
В корзину
Прислать комментарий

Условие

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

Подсказка

Можно ли что-нибудь сказать про членов компании А и В, если А знает В (если А не знает В)?

Решение

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

Ответ

N-1.


© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .